142. Linked List Cycle II - jiejackyzhang/leetcode-note GitHub Wiki

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

解题思路与141. Linked List Cycle类似，采用一快一慢两个指针，如果两指针相遇，则说明有cycle。

这里如果一开始令p1，p2都从head开始，则当它们相遇时，p1走了k步，p2走了2k步。 若设cycle的长度为r，p2比p1多走了nr步，即k=nr。

令head到cycle起始点为s步，相遇点到cycle起始点为m步。 则s = k-m = nr-m = (n-1)r + (r-m)。 因此，若p1从head出发，p2从相遇点出发，每次前进一步，则它们相遇时恰好就在cycle起始点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode p1 = head;
        ListNode p2 = head;
        boolean isCycle = false;
        while(p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2) {
                isCycle = true;
                break;
            }
        }
        if(!isCycle) return null;
        p1 = head;
        while(p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}