Linked List Cycle

You'll find a cycle with fast and slow pointers, using no extra memory. You need linked list nodes and Python's is. Related chapter: linked lists.

1. The problem

You get the head of a linked list. Return whether following next from the head ever reaches the same node twice. Repeated values don't make a cycle; reaching the same node again does. You get only the head, not where the cycle starts. This is LeetCode 141.

2. A correct baseline

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def baseline(head):
    seen = set()
    while head is not None:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

def example():
    a, b, c = ListNode(1), ListNode(2), ListNode(3)
    a.next, b.next, c.next = b, c, b
    return a

assert baseline(example())
assert not baseline(ListNode(7, ListNode(7)))
assert not baseline(None)

This doesn't change the list. For n nodes, it takes O(n) time and O(n) extra memory. On a million nodes, the set holds a million entries.

The bottleneck. The time is already as good as it gets. The waste is memory: it stores every node just to notice a repeat.

3. The observation

Picture two runners on a track. If the track is a straight line, the fast runner reaches the end. If it loops, the fast runner laps the slow one and they meet.

Do the same with two pointers. slow moves one node per step, and fast moves two. Without a cycle, fast reaches None. In a cycle, fast gains one node per step on slow, so the gap shrinks by one each step until they meet. Two pointers replace the whole set.

4. The solution and a trace

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

class Solution:
    def hasCycle(self, head) -> bool:
        """Detect a cycle without changing a singly linked list."""
        slow = fast = head  # Reachable finite nodes; each has one next link.
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            # Compare node identity after moving, not their stored values.
            if slow is fast:
                return True
        return False

solve = Solution().hasCycle
assert solve(example())
assert not solve(ListNode(7, ListNode(7)))
assert not solve(None)

Trace A → B → C → B:

5. Why it works

No cycle means False. After t steps, slow is t nodes in and fast is 2t nodes in. Without a cycle, those are different nodes for any t > 0, so they never meet. fast reaches None and the loop ends.

A cycle means True. Say the cycle has L nodes. Once both pointers are inside it, fast gains one node per step. So the gap between them shrinks by one each step, and they meet within L steps.

A finite list either ends or loops, so these two cases cover everything.

6. Cost, edge cases, and failure

Cost. O(n) time, growing in step with the list, even when a straight part leads into the cycle. O(1) extra space.

Edge cases. A node that points to itself is a cycle. Compare only after moving: both pointers start at the head, so comparing first would call every list a cycle.

Where it fails. Comparing values instead of nodes gives wrong answers:

head = ListNode(7, ListNode(7, ListNode(7)))
assert head.next.val == head.next.next.val
assert head.next is not head.next.next
assert not solve(head)
one = ListNode(9)
one.next = one
assert solve(one)

import random
rng = random.Random(141)
for _ in range(1000):
    nodes = [ListNode(rng.randrange(3)) for _ in range(rng.randrange(40))]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if nodes and rng.randrange(2):
        nodes[-1].next = rng.choice(nodes)
    head = nodes[0] if nodes else None
    links = [node.next for node in nodes]
    assert solve(head) == baseline(head)
    assert all(node.next is link for node, link in zip(nodes, links))