Problem
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?
Solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
var slow = head;
var fast = head;
var entry = head;
while (slow && fast) {
slow = slow.next;
fast = fast.next ? fast.next.next : undefined;
if (slow === fast) {
while (entry !== slow) {
entry = entry.next;
slow = slow.next;
}
return entry;
}
}
return null;
};
Explain:
fast
每次走两步,slow
每次走一步,如果链表有环的话,它们最终会相遇。
设:
x
为head
到环起点的长度y
为环的长度a
为环起点到fast
和slow
相遇点的长度b
为fast
和slow
相遇点到环起点的长度
则有:
fast
走的长度为x + a
slow
走的长度为x + y + a
(x + y + a) / (x + a) = 2
推出:y = x + a; x = y - a = b;
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).