###### tags: ` leetcode`
142.Linked List Cycle II
===

想法：
只要不是有迴圈的，就直接斷出。
有迴圈的就直接去找，有就回給去。

解法：
此題是有兩種解法。
Ａ、暴力解
一個之前走過的位置通通放到一個table裡面，若table裡面有重複的，就直接print出來。
B、迴圈解
使用快慢指針。這個迴圈開始處離head有A步，走了B步快慢指針在迴圈裏頭交會，再走C步會回到迴圈起始點。
然後把慢指針拉回head，快慢指針開始一次都只走一格，最後交會在迴圈起始處。

推論:
慢指針:
a+b
快指針(b+c是一圈，他應該繞了好幾圈才碰到):
a+n(b+c)+b

2(a+b)=a+n(b+c)+b
a=(n-1)b+c

拉回來之後一次走一個，確認最終快指針會繞幾圈+C的一個距離，在起始點一起相會。

程式碼：
A、

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        lookup = set()

        while cur:
            if cur in lookup:
                return cur
            lookup.add(cur)
            cur=cur.next
        return None

B、

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
	// 若根本一開始就NULL 也不用測
        if not head: return
        slow,fast = head,head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                break
        //若發現沒有迴圈，也直接退出    
        if not fast.next or not fast.next.next:
            return 

        slow = head
        while slow.next:
            if fast == slow:
                return slow
            slow=slow.next
            fast=fast.next
        return