Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Linked List Cycle II

Find the node where a cycle in a linked list begins, using fast and slow pointers and O(1) extra space, with a proof of why the method works.

Updated Medium read: 7 min read

Approaches at a glance

ApproachTimeSpace
Hash set of visited nodesO(n)O(n)
Fast and slow pointersO(n)O(1)

The problem

A linked list normally ends with a node whose next is null. In a list with a cycle, the last node points back to an earlier node instead, so following next goes round for ever.

Given the head of a list, return the node where the cycle begins: the first node that would be visited twice. If there is no cycle, return null. The list must not be modified.

3 → 2 → 0 → -4
    ↑        │
    └────────┘         →  the node holding 2
 
1 → 2
↑   │
└───┘                  →  the node holding 1
 
1 → null               →  null (no cycle)

The answer is a node, not a value or a position. Two different nodes can hold the same value.

A node, in each language. All the code on this page uses this shape:

JavaScript

// A node is any object with a value and a next.
const node = { value: 1, next: null };

Python

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

Approach 1: hash set of visited nodes

Walk the list, remembering every node passed. The first node that is already in the set is where the cycle begins. Reaching null means there is no cycle.

JavaScript

function detectCycleWithSet(head) {
  const visited = new Set();
  for (let node = head; node !== null; node = node.next) {
    if (visited.has(node)) return node;
    visited.add(node);
  }
  return null;
}

Python

def detect_cycle_with_set(head):
    visited = set()
    node = head
    while node is not None:
        if node in visited:
            return node
        visited.add(node)
        node = node.next
    return None

The set stores the node objects themselves, so two nodes with equal values are still told apart.

Time O(n). Space O(n) for the set. It is simple and correct; the challenge is to do without the extra memory.

Approach 2: fast and slow pointers

This uses the first technique from the linked list pointers pattern, in two phases.

Phase 1: find out whether there is a cycle. Start two pointers at the head. Move slow one node at a time and fast two. If fast reaches the end, there is no cycle. If there is a cycle, fast goes round it and eventually lands on slow.

Phase 2: find where the cycle begins. Leave slow at the meeting point. Start a new pointer at the head. Move both one node at a time. The node where they meet is the start of the cycle.

JavaScript

function detectCycle(head) {
  let slow = head;
  let fast = head;
 
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
 
    if (slow === fast) {
      let finder = head;
      while (finder !== slow) {
        finder = finder.next;
        slow = slow.next;
      }
      return finder;
    }
  }
  return null;
}

Python

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

Phase 1 is easy to believe. Phase 2 looks like a coincidence until the distances are written down.

Walkthrough

3 → 2 → 0 → -4, with -4 pointing back to 2:

Phase Step slow fast finder
1 Start 3 3
1 1 2 0
1 2 0 2
1 3 -4 -4 They meet
2 Start -4 3
2 1 2 2

In the third step of phase 1, fast goes from 2 to 0 to -4 and lands on slow. In phase 2, one step takes finder from 3 to 2 and slow from -4 round to 2. They meet on the node holding 2, which is the answer.

Time O(n): slow meets fast before completing its first lap of the cycle, and phase 2 takes no more steps than the distance from the head to the cycle. Space O(1).

Why phase 2 works

Give the distances names, counted in steps:

head ──── a ────→ cycle start ──── b ────→ meeting point
                       ↑                        │
                       └──── rest of cycle ─────┘
 
a = from the head to the start of the cycle
b = from the start of the cycle to the meeting point
c = the length of the whole cycle

When the pointers meet:

  • slow has taken a + b steps.
  • fast has taken twice as many: 2(a + b).

Both are standing on the same node, and fast got there by going round the cycle some whole number of extra times. So the difference between their distances is a whole number of laps:

2(a + b) − (a + b) = a + b = (some whole number) × c

In words: walking a + b steps from the start of the cycle brings you back to the start of the cycle.

Now look at where slow is: b steps past the start of the cycle. If it walks another a steps, it will have gone a + b steps past the start in total, which by the line above puts it exactly back on the start.

And a is also the distance from the head to the start of the cycle. So a pointer leaving the head and a pointer leaving the meeting point, both moving one step at a time, arrive at the start of the cycle after exactly a steps, at the same moment. That is where they meet.

Checking with the walkthrough: a = 1 (from 3 to 2), b = 2 (from 2 to -4) and c = 3. Indeed a + b = 3, one whole lap.

Why the pointers must meet in phase 1

Once both pointers are inside the cycle, think of fast as chasing slow. Each step, fast moves two nodes and slow moves one, so the gap between them closes by exactly one. A gap that shrinks by one each step cannot skip past zero. fast never jumps over slow.

Try it yourself

Copy a solution from above, add the lines below, and run it. The Python version also needs the ListNode class from the top of the page. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

const a = { value: 3, next: null };
const b = { value: 2, next: null };
const c = { value: 0, next: null };
const d = { value: -4, next: null };
a.next = b;
b.next = c;
c.next = d;
d.next = b; // the last node points back to b
 
console.log(detectCycle(a).value); // 2
console.log(detectCycle({ value: 1, next: null })); // null

Python

a, b, c, d = ListNode(3), ListNode(2), ListNode(0), ListNode(-4)
a.next = b
b.next = c
c.next = d
d.next = b  # the last node points back to b
 
print(detect_cycle(a).value)  # 2
print(detect_cycle(ListNode(1)))  # None

The comment after each line is the result you should see.

Common mistakes

  • Comparing values instead of nodes. slow.value === fast.value gives false matches whenever two nodes hold the same value. Compare the nodes: slow === fast.
  • Checking only fast !== null. fast takes two steps, so fast.next must exist too, or the second step reads next of null.
  • Comparing before moving. Both pointers start on the head, so a check at the top of the loop reports a meeting immediately. Move first, then compare.
  • Moving slow two steps in phase 2. Both pointers move one step at a time in the second phase. The proof depends on it.
  • Returning the meeting point. The pointers usually meet somewhere inside the cycle, not at its start. Phase 2 is not optional.

Original problem: LeetCode 142: Linked List Cycle II