How do you find the node where a cycle begins in a linked list?
Detect the cycle with slow and fast pointers. When they meet, reset one pointer to the head and move both one step at a time. They meet again exactly at the start of the cycle.
Explain it simply
Imagine a running track with a straight road leading to it. Two runners start at the gate, one at double speed. If they meet on the track, here is the neat fact: the distance from the gate to the track entrance equals the distance from the meeting point forward to the entrance (going around the loop).
So after they meet, send one runner back to the gate and let both walk at the same speed. They arrive at the entrance together.
Example
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function fromArray(arr) {
const dummy = new ListNode(0);
let tail = dummy;
for (const v of arr) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
function toArray(head) {
const out = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function cycleStart(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
const head = fromArray([1, 2, 3, 4, 5]);
let tail = head;
while (tail.next) tail = tail.next;
tail.next = head.next.next; // 5 points back to node 3
console.log(cycleStart(head).val); // Output: 3Complexity
Time O(n), space O(1).
What to say in the interview
"I run Floyd's slow and fast pointers until they meet. Then I restart one pointer from the head and move both one step at a time; the node where they meet again is the cycle start. The math works because the head-to-start distance equals the meeting-point-to-start distance around the loop. Time O(n), space O(1)."
Common mistakes
- Returning the meeting point instead of the start of the cycle.
- Using a Set of visited nodes without mentioning it costs O(n) memory.