142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example：

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

image

Note：

Note: Do not modify the linked list.

解释下题目：

找到有循环的链表的循环起始点

1. 两个指针

实际耗时：0ms

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            // found cycle
            ListNode listNode = head;
            while (listNode != slow) {
                listNode = listNode.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    return null;
}

  思路用下面的图来解释就很好了。

解释图

在该算法中，fast是一次走两步，slow是一次走一步，直到它们相遇（如果不相遇说明压根没有环），于是就有以下的公式：

fast = a+b+n*(b+c)
slow = a+b+m*(b+c)
fast = 2*slow

通过变形易得：c-a=(2*m-n+1)*(b+c) 而（b+c）是一圈，所以其实重复多少次也无所谓的。所以说c与a只需要多走几圈就可以追到，也就是在b点开始走a+x(b+c)就可以到。就有了上面的代码。

时间复杂度O(n)

空间复杂度O(1)

---