LeetCode OJ 142. Linked List Cycle II

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?

这个题还是蛮考验数学推理的，不过在前一个题的基础上还是能推出结果的。这是英文一段解释，非常有帮助。

First Step: Assume the first pointer runs from head at a speed of 1-by-1 step, as S, and the second pointer runs at a speed of 2-by-2 step, as 2S, then two pointers will meet at MEET-POINT, using the same time. Define outer loop is A, the distance from CIRCLE-START-POINT to MEET-POINT is B, and the distance from MEET-POINT to CIRCLE-START-POINT is C (Apparently, C=loop-B), then (n*loop+a+b)/2S = (a+b)/S, n=1,2,3,4,5,....

Converting that equation can get A/S=nloop/S-B/S. Since C=loop-B, get A/S = ((n-1)loop+C)/S.

That means, as second step, assuming a pointer running from head and another pointer running from MEET-POINT both at a speed S will meet at CIRCLE-START-POINT;

代码如下：

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         if(head==null || head.next==null) return null;
 4         ListNode pointer1 = head;
 5         ListNode pointer2 = head;
 6         
 7         while(pointer1!=null && pointer2!=null){
 8             pointer1 = pointer1.next;
 9             if(pointer2.next==null) return null;
10             pointer2 = pointer2.next.next;
11             
12             if(pointer1==pointer2) break;
13         }
14         if(pointer1==null || pointer2==null) return null;
15         
16         pointer1 = head;
17         while(pointer1 != pointer2){
18             pointer1 = pointer1.next;
19             pointer2 = pointer2.next;
20         }
21         return pointer1;
22     }
23 }