Linked List Cycle

Given the head of a linked list, determine if the list has a cycle.

Why this is worth learning

Pointer identity describes topology; equal values do not create a cycle. Two speeds exploit a deterministic next-pointer graph without allocating a visited set.

Before coding: one-minute experiment

Can an acyclic list whose node values are [7,7,7] be declared cyclic by value equality?

Function signature

func HasCycle(head *ListNode) bool

Inputs / outputs

• head: pointer to the first node.
• Return: true if there is a cycle.

Example

1 -> 2 -> 3 -> 4
     ^         |
     |_________|
Output: true

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

A correct baseline follows Next pointers and stores every visited pointer in a set. Seeing a pointer twice proves a cycle; reaching nil disproves one. The set costs O(n) space. To remove it, exploit that each node has exactly one successor: use two walkers with different speeds. Once both are inside a cycle of length c, their relative offset changes by one modulo c each round, so equality must occur within c rounds. This derives Floyd's one-step/two-step method. Comparing before the first movement would instead report the shared initial head as a cycle.

Invariant: after t iterations, slow has followed t edges and fast 2t edges from head. Once both are in the cycle, their relative offset advances by one modulo its length.

Algorithm (step-by-step)

1. Initialize slow = head, fast = head.
2. While fast and fast.Next are not nil:
   • Move slow one step.
   • Move fast two steps.
   • If they meet, return true.
3. Return false.

Correctness sketch

If the list is acyclic, the fast pointer eventually reaches nil or a node whose next is nil, so the guarded loop returns false. If a cycle exists, both pointers eventually enter it. Thereafter their relative position changes by one edge per iteration modulo the cycle length because fast moves two edges and slow one. Within at most one cycle length their relative offset becomes zero, so they meet at the same node and return true. The equality test occurs after movement, avoiding the trivial initial equality at head. No next pointers are changed.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3 -> 4
     ^         |
     |_________|
Output: true

Walk:
- initially slow=1, fast=1; do not treat this initial equality as a meeting
- after 1 iteration: slow=2, fast=3
- after 2 iterations: slow=3, fast=2 (fast follows 3->4->2)
- after 3 iterations: slow=4, fast=4 -> meet -> cycle exists

Pitfalls to avoid

• Not checking fast.Next before advancing.

Debugging lens

Include nil, a self-loop, a cycle entering at head, and a long non-cyclic prefix. Check fast and fast.Next before dereferencing two steps.

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

On A→B→C→D→E→C, put slow and fast at A and advance before comparing. At which node do they first meet? Would changing every Val to 0 affect the result?

Return to Linked List · Module quiz