LeetCode 141 · Linked List

Linked List Cycle, explained with a picture

Tortoise and hare on a looping track.

EasyLinked List
▶ Watch it step by step

The problem

Given a linked list, decide whether it has a cycle: does following next pointers ever loop back to an earlier node?

Input:  3 → 2 → 0 → −4, and the last node links back to position 1
Output: true

Picture it

Picture a tortoise and a hare on the track. The tortoise moves one coach at a time, the hare two. If the track simply ends, the hare falls off the end: no cycle. If the track loops, the hare laps around and must eventually land on the same coach as the tortoise.

How to recognise it

  • You follow "next" links and need to know whether the walk ever comes back to a node it has visited.
  • If there is no cycle, the walk ends at None. If there is one, it goes round forever, so a plain walk cannot tell "very long" from "endless".
  • The follow-up asks for O(1) memory, which rules out remembering visited nodes.
  • The same "fast and slow pointer" trick (Floyd's cycle detection) works on anything that maps a state to one next state: Happy Number, Find the Duplicate Number, random-number generators.

Start with brute force

Remember every node you have visited in a set. If you reach a node that is already in the set, the list loops.

def has_cycle_brute(head):
    seen = set()
    node = head
    while node:
        if node in seen:
            return True
        seen.add(node)
        node = node.next
    return False

Python hashes plain objects by identity, so two nodes with the same value are still different keys. Time is O(n) and space is O(n). With LeetCode's 10^4 nodes it is fast; the cost is the set of up to 10^4 references, which the follow-up asks you to avoid.

From brute force to the idea

  1. Find the waste. The set stores every node only to notice one repeat. You do not need to know where the loop is, only whether there is one.
  2. Race two pointers. slow moves one node per step and fast moves two. Both start at the head.
  3. No cycle: fast falls off. If the list ends, fast or fast.next becomes None first, the loop condition fails, and the answer is False.
  4. A cycle: fast catches up. Once both are inside the loop, fast gains exactly one node per step on slow. The gap shrinks by one each time, so it reaches zero within one lap, and they land on the same node. It can never jump over slow, because it closes the gap one node at a time.
  5. Compare identity. slow is fast asks "the same node?", not "the same value?".

This is the key idea: a pointer moving twice as fast must either reach the end or lap the slow one.

The key idea

Floyd’s fast/slow pointers: they meet if and only if there is a cycle. O(n) time, O(1) space.

Python solution

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

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n): each node is visited and added to the set onceO(n): the set of visited nodes
Fast and slow (shown code)O(n): slow enters the loop within n steps, then they meet within one more lapO(1): two references

Edge cases

  • Empty list: fast is None, the loop is skipped, and the code returns False.
  • One node, no cycle: fast.next is None, so it returns False.
  • One node pointing to itself: after one step both pointers are back on that node, so it returns True.
  • Two nodes pointing at each other: returns True.
  • Cycle that starts late (3 → 2 → 0 → −4, with −4 linking back to 2): returns True. They meet somewhere in the loop, not necessarily at its start.
  • Repeated values without a cycle (1 → 1 → 1): returns False, because nodes are compared with is, not by value.

Common mistakes

  • Comparing slow.val == fast.val. A list like 1 → 1 → 1 would be reported as a cycle.
  • Checking slow is fast before moving the pointers. They both start at the head, so the check succeeds at once.
  • Looping while fast.next and fast.next.next without checking fast: on an empty list fast.next raises AttributeError.
  • Moving fast three steps at a time "to be quicker". It still works, but it is no faster in big-O and makes the meeting point harder to reason about.
Your turn: where does the cycle start?

Return the node where the cycle begins, or None if there is no cycle. For 3 → 2 → 0 → −4 with −4 linking back to 2, return the node holding 2. Use O(1) memory. Describe your approach, then write it if you like.

Compare with our answer

First find a meeting point exactly as before. Then move one pointer back to the head and advance both one step at a time: they meet again at the cycle's start. The reason: if the start is a steps from the head, the meeting point is also a steps (plus some whole laps) before the start, going round the loop.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

Time O(n), space O(1).

A strong answer mentions: the first meeting only proves a cycle, resetting one pointer to the head, both moving at the same speed in phase two, and the distance argument for why they meet at the start.

Check what stuck

1. Repeatedly replace a number by the sum of the squares of its digits. Decide whether it ever reaches 1, using O(1) memory. Which approach fits best?

2. Why are the fast and slow pointers guaranteed to meet when there is a cycle?

3. A learner moves if slow is fast: return True to the top of the loop, before the pointers move. What happens?

Score 60% or more and the lesson is marked complete.