###### tags: `Leetcode` `medium` `list` `pointer` `python` `Top 100 Liked Questions`

# 142. Linked List Cycle II

## [題目連結]:https://leetcode.com/problems/linked-list-cycle-ii/

## 題目:
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.


#### [圖片來源:] https://leetcode.com/problems/linked-list-cycle-ii/

## 解題想法:
* 題目為給一個list，若有cycle，求cycle起始位置，否則回傳None
* 題目給的pos只是驗證時說明尾巴要連到哪個node，不會當成參數傳遞

* 使用pointer:
* fast=head
* slow=head
* 燒腦說明:

        A           B
head-----------x========y
                |       |
                |_______|
                    C     
                    

*
* 設head到環的**起始位置**(x)距離為A
* 從x走到slow、fast**相遇地點**(y)距離為B
* 從y走回x距離為C
* 則: **fast走到y**:
* A+ n圈的(B+C)+B
* 也相當於2倍的**slow** = 2 **(A+B)**
* 所以得到 A+n(B+C)+B=2(A+B)
* 化簡得到: A=(n-1)(B+C)+C
* 即: **起點到x** = **走n-1圈的loop+C的距離**
* 所以再令:
* start=head
* tail=相遇位置(y)
* 分別向前走則相遇地點即為(x)

* 解釋:
* 概念: 讓A與 (B~C)loop產生關聯
* 由上得知A=n-1圈的loop + C
* 最終fast、slow相遇在y，
* 此時讓start從head出發，一步一步走
* 同時讓fast從y一步一步走，走(n-1)圈B~C loop後，還是在y，然後再走一段C
* 此時start走了A的距離，到達x ;
* fast走了(n-1)loop+c的距離->等於也走了A的距離，也到達了x !!!

## Python:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow=head
        fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            #相遇
            if slow==fast:
                start=head
                while start!=fast:
                    fast=fast.next
                    start=start.next
                return start
        return None
    
head=ListNode(3)
head.insert(2)
head.insert(0)
head.insert(-4)
head.next.next.next.next=head.next

result= Solution()
ans=result.detectCycle(head)
print("loop起點:",ans.val) #loop起點: 2