Module 11 · Linked Lists and Pointer Mutation

105. Detect a Cycle

Bridge · Download this solution · All solutions and shared helpers

Problem

Return whether following next links from head eventually revisits a node. Values may repeat without creating a cycle. Use constant auxiliary space and leave links unchanged. None is acyclic.

Examples

Example 1

head = build_list([1,2,3]); head.next.next.next = head.next
has_cycle(head)
=> True

The tail returns to the second node.

Example 2

has_cycle(build_list([1,1]))
=> False

Equal values do not imply equal node identities.

Example 3

has_cycle(None)
=> False

No links can form a cycle.

Reveal the worked solution and reasoning

Why this mechanism works

Inside a cycle, a fast pointer gains one step per iteration on a slow pointer. Their relative position modulo the cycle length must eventually become zero. In an acyclic list the fast pointer reaches the end instead, providing the other termination condition.

State and boundaries

slow moves one link and fast moves two. Equality is tested by node identity after movement, not by equal stored values.

Protocol

Start both pointers at head.
Guard the fast two-step movement.
Advance slow once and fast twice.
Return True if they are the same node.
Return False when fast reaches the end.

Visualization

1 -> 2 -> 3
     ^    |
     +----+
fast gains one cycle position per round

Python implementation

from structures import build_list

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

has_cycle(head)

L4 has_cycle: slow = fast = head
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N1(val=1,next=N2,random=None)

L6 has_cycle: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N1(val=1,next=N2,random=None)

L7 has_cycle: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N3(val=3,next=N2,random=None)

L6 has_cycle: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=N2,random=None); fast=N3(val=3,next=N2,random=None)

Result: True. The tail returns to the second node.

has_cycle(build_list([1,1]))

L4 has_cycle: slow = fast = head
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N1(val=1,next=N2,random=None)

L6 has_cycle: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=1,next=None,random=None); fast=N1(val=1,next=N2,random=None)

L7 has_cycle: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=1,next=None,random=None); fast=None

Result: False. Equal values do not imply equal node identities.

Why the solution is correct

Without a cycle, fast eventually reaches None and no repeated-node meeting after movement is possible. With a cycle, both enter it and the relative offset advances by one modulo its length, guaranteeing a meeting within one cycle traversal.

Time and space

O(n) time in the number of reachable distinct nodes and O(1) auxiliary space.

Common mistakes

Comparing values confuses duplicate data with shared nodes. Testing equality before the first movement falsely detects a cycle in every nonempty list.

Reasoning card

State: slow moves one link and fast moves two. Equality is tested by node identity after movement, not by equal stored values.

Invariant: Without a cycle, fast reaches None.

Decision to rehearse: Fast eventually meets slow inside a cycle.

Finish: Return False when fast reaches the end

Transfer exercise

After finding a meeting, walk once around the cycle to determine its length.