Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return nil.

Why this is worth learning

The first meeting locates a point in the cycle, not necessarily its entrance. A second equal-speed phase uses the modular distance accumulated by Floyd's traversal.

Before coding: one-minute experiment

For a list 0→1→2→3→4→2, which node must be returned, even if the first meeting is elsewhere?

Function signature

func DetectCycle(head *ListNode) *ListNode

Inputs / outputs

• head: pointer to the first node.
• Return: the node where the cycle starts, or nil if no cycle.

Example

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|
Cycle starts at node with value 3.

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

A pointer set can return the first node encountered twice; that is the entry. Floyd saves the set but initially returns a different fact: two walkers met somewhere in the cycle. Let a be the prefix length, c the cycle length, and t the slow walk length at their meeting. Fast has walked 2t, so their difference t is a multiple of c. The meeting is t−a past the entry, hence moving another a steps reaches the entry modulo c. Reset one walker to head and move both one step: the head walker cannot meet a cycle node before reaching the entry, and both arrive there after a steps.

Invariant: if the prefix length is a and the cycle length is c, the meeting point is a steps before the entry modulo c. The reset pointer reaches the entry after exactly a steps; the other pointer may make additional full laps in that time.

Algorithm (step-by-step)

1. Run fast/slow pointers to detect a cycle.
2. If no cycle, return nil.
3. Reset one pointer to head.
4. Move both pointers one step at a time until they meet; return that node.

Correctness sketch

Let a be the distance from head to the cycle entry, c the cycle length, and t the slow pointer's steps at a meeting. The fast pointer has traveled 2t, so their difference t is a multiple of c. The meeting point's offset from entry is (t-a) modulo c, meaning it is a steps modulo c before the entry. Reset one pointer to head and advance both one edge at a time. After a steps the reset pointer reaches the entry and the meeting pointer also reaches it. Before that, the reset pointer is outside the cycle, so they cannot meet earlier. If the first phase reaches nil, no entry exists.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|
Cycle starts at node with value 3.

Walk:
- detect: slow=1, fast=1 -> step to slow=2 fast=3 -> slow=3 fast=5 -> slow=4 fast=4 meet
- reset p1=head(1), p2=4: step -> p1=2 p2=5; step -> p1=3 p2=3
- cycle start at node value 3

Pitfalls to avoid

• Returning the meeting node instead of the cycle entry.

Debugging lens

Test cycles of length one after a nonempty prefix and cycles starting at head. Return the original entry pointer, never a newly allocated node with an equal value.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Guard the loop with fast != nil && fast.Next != nil.
• Compare node pointers, not values.

Reconstruction checkpoint

A list enters a four-node cycle after five edges. Floyd meets after eight slow steps. How far is that meeting past the entry, and why do five equal-speed reset steps still reach the entry?

Return to Linked List · Module quiz