Linked List Cycle II
Return the node where a linked list's cycle begins, or null, using Floyd's cycle detection and a second walk from the head, in O(1) extra space.
Problem Understanding
Linked List Cycle II: given the head of a linked list, return the node where the cycle begins, or null if there is no cycle. LeetCode describes the input with pos, the index the tail's next points to (-1 for none); pos is not passed to your function. Do not modify the list.
Examples: [3,2,0,-4], pos 1 → the node at index 1; [1,2], pos 0 → index 0; [1], pos -1 → null.
The Intuition: Two Walks of the Same Length
Phase 1 is Linked List Cycle: slow moves one node, fast moves two. If fast reaches the end there is no cycle; otherwise they meet somewhere inside the cycle.
Phase 2 uses some arithmetic. Say the cycle starts a nodes from head and they met b nodes into a cycle of length c:
slowwalkeda + b;fastwalked2(a + b).- The extra
a + bthatfastwalked is a whole number of laps, soa + bis a multiple ofc. - From the meeting point,
amore nodes completes those laps and ends at the cycle start. - So send
slowback to head and move both one node at a time: afterasteps both are at the start.
The same slow and fast pointers solve Middle of the Linked List and Find the Duplicate Number, which is this exact problem in disguise.
Interactive Walkthrough
POS = 1 · TAIL → #1
START AT HEAD
head slow fast
#0
→
#1
→
#2
→
#3
↺ back to #1
Phase
1
Moves
0
Answer
:
slow and fast both start at head, #0 (3)
Next
fast is #0 (3) and fast.next is #1 (2): both exist, keep running
Values
pos
Legend & Complexity
slow: one node per step; back at head in phase 2
fast: two nodes per step, then one in phase 2
The node where the cycle begins
↺ back to …: the tail’s next points back into the list
Time
O(n)
Space
O(1)
slow and fast are named above their nodes, and the row ends ↺ back to #k where the tail links back. Watch where they meet, then the second walk. Try Long tail to see the meeting point and the start come apart.
Dry Run Table
Input: [3,2,0,-4], tail → #1 (a = 1, c = 3).
| Step | slow | fast | Note |
|---|---|---|---|
| start | #0 | #0 | |
| move 1 | #1 | #2 | |
| move 2 | #2 | #1 | fast went #3 → #1 |
| move 3 | #3 | #3 | meet: a cycle exists |
| reset | #0 | #3 | slow back to head |
| walk 1 | #1 | #1 | meet again |
Answer: the node at index 1 (value 2). Here a + b = 1 + 2 = 3, one full lap.
The Solution Template
Phase 1 detects, phase 2 runs inside the if.
Linked List Cycle II Code
1var detectCycle = function(head) {2 let slow = head, fast = head;3 while (fast && fast.next) {4 slow = slow.next;5 fast = fast.next.next;6 if (slow === fast) {7 slow = head;8 while (slow !== fast) {9 slow = slow.next;10 fast = fast.next;11 }12 return slow;13 }14 }15 return null;16};
Edge Cases & Common Mistakes
- Returning the meeting point: it is inside the cycle but usually not its start.
- Moving fast two steps in phase 2: both pointers must move one node at a time.
- Cycle starting at head: they meet and the walk from head is already there; the inner loop runs 0 times.
- Empty list or one node without a loop: the
whilecheck fails at once; return null. - Comparing values instead of nodes: values can repeat; compare the node references.
Summary
Run slow and fast until they meet (or fast ends: no cycle). Then reset slow to head and move both one node at a time; they meet at the cycle start. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet