Does the chain loop back on itself?

Linked lists Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Pick the fix

Inside a loop, the fast pointer is 3 links behind the slow one. How many steps until they meet?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3

Right: the gap shrinks by one per step.

Because the gap closes one link at a time, the meeting happens within one lap, which keeps the whole check linear.

Why not the others?
  • B 6. Only the difference in speed matters, and that is one link per step.
  • C It might never meet. A gap that drops by one each step must reach zero.
Slow and fast pointers moving along a chain whose tail joins link 2, until they meet, and along a chain with no loop, until the fast pointer runs off the end.

Steps come from running the Python solution.

Text version

Tail joins link 2:

Links [3, 8, 1, 6, 4]; the last link points back to link 2.

  1. slow = 1, fast = 2. Slow at 8, fast at 1
  2. slow = 2, fast = 4. Slow at 1, fast at 4
  3. slow = 3, fast = 3. Slow at 6, fast at 6: they meet, so there is a loop

Result: true

No loop:

Links [3, 8, 1, 6].

  1. slow = 1, fast = 2. Slow at 8, fast at 1
  2. slow = 2, fast = end. Slow at 1, fast at end
  3. slow = 2, fast = end. Fast reached the end: no loop

Result: false

30-second answer

Send a slow pointer one link per step and a fast pointer two. Without a loop the fast pointer reaches the end. With a loop, once both are inside it the fast one gains one link per step, so it lands on the slow one within one lap. O(n) time, O(1) memory.

Practise saying it · 45 s. No recording, just a timer

Explain loop detection with two speeds.

Say your answer out loud, then check which of these points you covered:

  • Slow 1, fast 2
  • Gap closes by 1
  • O(1) memory

Deep dive

A set of seen links also works in O(n) time but O(n) memory.

Compare links by identity (is), not by value; values can repeat.

After they meet, restarting one pointer from the head and stepping both by one finds where the loop starts.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def has_loop(head: Link | None) -> bool:
    slow = fast = head
    while True:
        if fast is None or fast.next is None:
            return False  # the quick pointer ran off the end
        fast = fast.next.next
        slow = slow.next if slow else None
        if slow is fast:
            return True

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun hasLoop(head: Link?): Boolean {
    var slow = head
    var quick = head
    while (true) {
        // the quick pointer ran off the end: no loop
        val step = quick?.next ?: return false
        quick = step.next
        slow = slow?.next
        if (slow === quick) return true
    }
}

Common mistakes

  • Checking fast.next.next without first checking fast.next.
  • Comparing values instead of links.

Senior take & follow-ups

Explain why the fast pointer cannot jump over the slow one: the gap shrinks by exactly one each step.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the first link of the loop?

    Show hint

    After the meeting, move one pointer to the head; step both by one; they meet at the loop's start.

  2. How long is the loop?

    Show hint

    From the meeting point, step one pointer until it returns, counting steps.

What each operation costs: Linked List · Singly Linked List · Doubly Linked List

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.