Fast and Slow Pointers

Concepts covered: Two-Pointer, Conditional Loops

The third shape sends 2 pointers from the same start at different speeds through a structure you can only walk forward: slow moves 1 node per step, fast moves 2. If the structure loops back on itself, the faster pointer comes around and catches the slower one from behind. If the structure ends, fast reaches None first. The question arrives as "does this linked list contain a cycle?" or "return the middle node", and what gets graded is whether the loop is correct, whether its stopping condition can crash, and whether you can say why the pointers must meet.

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


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

The line that crashes

The failure that costs the round is the guard. fast = fast.next.next takes 2 hops, which means fast has to exist before the line runs and so does fast.next. A loop written while fast: passes every cyclic test and fails on an acyclic list with an odd number of nodes. There fast lands on the last node, where fast.next is None, so the 2-hop line raises AttributeError: 'NoneType' object has no attribute 'next'. The interviewer tests it with 1 node or 3 nodes and no cycle. Even lengths pass by luck, because fast steps from the second-to-last node straight onto None and the loop exits. The is comparison rather than == is the second detail: 2 different nodes can carry the same value, and identity is what cycle detection asks about.

The animation stands in for the linked list with an array of next indexes, nxt[i] being the node that node i points to, with -1 marking the end. Node 5 points back to node 2, so nodes 2 through 5 form a loop of 4. Watch the gap between the 2 pointers close by 1 each step once both are inside the loop.

nxt = [1, 2, 3, 4, 5, 2]   # node i points to nxt[i]; node 5 loops back to 2
slow = fast = 0
steps = 0
while fast != -1 and nxt[fast] != -1:
    slow = nxt[slow]
    fast = nxt[nxt[fast]]
    steps += 1
    if slow == fast:
        print("met at node", slow, "after", steps, "steps")
        break

met at node 4 after 4 steps

Why they must meet

Once both pointers are inside the loop, the distance from fast around to slow shrinks by exactly 1 each step, because fast gains 2 and slow gives back 1. A gap that starts at no more than the loop length and shrinks by 1 per step reaches 0 within 1 lap, which is why the meeting is a certainty, and why the whole run is O(n) with 2 references of extra space. The run above meets at node 4 after 4 steps. Say "the gap closes by 1 each step, so they meet within 1 lap of the cycle", and the interviewer hears a proof instead of a hope.

Set of visited nodes

• Correct in 4 lines, which is why most candidates write it first
• O(n) extra memory, 1 entry per node visited
• Needs the node to be hashable, which a plain object is
• Answers the question and fails the follow-up about space

Fast and slow pointers

• 7 lines, correct, with a guard that must be right
• O(1) extra memory, 2 references
• Works on any forward-only structure, including one you cannot store
• Answers the question and the follow-up in the same loop

Middle node, the same walk with a different stop

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

The guard and the 2 moves are unchanged, and the function returns slow when fast runs out. The follow-up is which middle you return on an even length: with 6 nodes slow stops on the 4th, and if the question wants the 3rd the guard becomes fast.next is not None and fast.next.next is not None, which stops fast 1 step earlier. State which middle you return before being asked, because the interviewer has a 6-node test ready and the answer depends on a line you have already written.

About this lesson

This section is part of the Two Pointers: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.