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.
找到一个链表的环的起点。
使用快慢指针的方法,先找到链表是否有环;
在快慢指针重合的地方,快指针正好比慢指针多走一个环的长度;
假设链表非环一共有K个元素,环有S个元素;
假设此时slow走了K+X步,那此时fast比它多走一个环,走了K+X+S步;
由于快指针一次走两步,(K+X+S)=2*(K+X);
S=K+X;
也就是说环上元素个数等于非环上元素个数加上slow已经在环上走过的;
那么找两个指针,同时从head和slow的位置往前走,他们应该在K步后会相遇,这就是我们要的元素。
var detectCycle = function(head) {
var slow = head, fast = head;
while(fast !== null && fast.next !== null) {
fast = fast.next.next;
slow = slow.next;
if (slow === fast) {
while (head !== slow) {
head = head.next;
slow = slow.next;
}
return slow;
}
}
return null;
};