linked list cycle ii


Linked List Cycle II
images
 t = X + mY + k
2t = X + nY + k
=> X + k = (m - 2n)Y 那么X+k关于Y互补,现在我们已经走了k步,再把其中一个指针指到head,再走X步就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode (ListNode head) {
if (head == null || head.next == null)
return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast != null && fast == slow) {
slow = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}

Reference 水中的鱼