142 Linked List Cycle II

题目

Linked List Cycle II

题解

首先要检测链表中是否存在环路，这里可以使用快慢指针的技巧，因为快指针与慢指针在存在环路的链表中必然会相遇。

digraph G {
    layout = circo
    A -> B -> C -> D
    D -> E -> F -> G -> H -> I -> J -> D
}

记链表中环路之前的部分长度为k，环路的长度为loop_size。当慢指针走了k步进入环路起始点时，快指针已经走了2k步，也就是已经走了k步进入环路并且在环路部分中又走了k步，此时快指针位于\(P = k \bmod loop\_size\)的位置。

如下图所示，慢指针位于环路起始处，快指针位于位置P，二者相距\(loop\_size - P\)个节点，由于慢指针每走一步快指针就走两步，快指针每次都会向慢指针多靠近一步，所以二者会在\(loop\_size - P\)步之后相遇，也就是说慢指针从环路起始处走\(loop\_size - P\)步之后的节点就是快慢指针相遇的节点。

由上图可知，快慢指针相遇的节点距离环路起始处的距离为P，而\(P = k \bmod loop\_size\)，也就是说从这个相遇节点出发，再走k步即可到达环路起始处，而从链表头到环路起始处的距离也为k，所以我们同时从链表头和相遇节点出发，走过k步之后必然会在环路起始处首次相遇。

代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None

        fast = head
        slow = head
        while fast is not None:
            fast = fast.next
            if fast is not None:
                fast = fast.next
            slow = slow.next

            if fast == slow:
                slow = head
                break

        if fast is None:
            return fast

        node1 = fast
        node2 = slow
        while node1 != node2:
            node1 = node1.next
            node2 = node2.next

        return node1