142. Linked List Cycle II

[chengchengxu15]

https://leetcode.com/problems/linked-list-cycle-ii/

Given 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. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

solution: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

[chengchengxu15]

hash table:

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:

        dict = {}
        while head != None and head.next != None:
            if head in dict:
                return head
            else:
                dict[head] = 1
                head = head.next
        return None

[chengchengxu15]

two pointers：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        if not head:
            return None
        if not head.next:
            return None
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            if fast == slow:
                break
        if fast == slow:
            while fast != head:
                fast = fast.next
                head = head.next
            return head
        else:
            return None

解释起来就有点麻烦了 假设有n个节点，在第m个节点开始循环，fast和low相遇在第s个节点，在相遇前fast跑完一次n之后又跑了n圈： 那么 fast跑过的距离：

• 2*s
• n + k(n-m) + (s-m) 2 * s = n + k(n-m) + s-m s = (k+1)(n-m) s = k(n-m) + n -m m = k(n-m) + n - s m = n -s (mod (n-m)) (n-m是环形列表的长度) 于是从两个新的指针，一个从head出发，一个从s出发，每次走一步，最后会在m点相遇。