Fast and Slow Pointers

Fast and slow pointers are two markers on a list that start apart and then move together. The gap between them turns a distance question into a single walk.

Recognition signal

A problem fits this pattern when it asks for a node a fixed distance from the end. Counting the length first would take an extra pass, and one pass is enough.

signals = [
    "Find a node a fixed distance from the end.",
    "One pass over the list is enough.",
    "The list length is not counted first."
]
for line in signals:
    print(line)

Template: gap then walk together

The template moves the fast marker K steps ahead, then walks both markers together. Two markers with a fixed gap is the pattern in plain words.

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.nxt = nxt

def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
        else:
            tail.nxt = node
        tail = node
    return head

def kth_from_end(head, k):
    fast = head
    for _ in range(k):
        fast = fast.nxt
    slow = head
    while fast is not None:
        slow = slow.nxt
        fast = fast.nxt
    return slow.value

print(kth_from_end(build([10, 20, 30, 40, 50]), 2))

Worked problem: first node as answer

When K equals the length of the list, the fast marker runs out at once. The slow marker never moves, so the first node is the answer.

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.nxt = nxt

def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
        else:
            tail.nxt = node
        tail = node
    return head

def kth_from_end(head, k):
    fast = head
    for _ in range(k):
        fast = fast.nxt
    slow = head
    while fast is not None:
        slow = slow.nxt
        fast = fast.nxt
    return slow.value

print(kth_from_end(build([5, 15, 25, 35]), 4))

Example

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.nxt = nxt

def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
        else:
            tail.nxt = node
        tail = node
    return head

def kth_from_end(head, k):
    fast = head
    for _ in range(k):
        fast = fast.nxt
    slow = head
    while fast is not None:
        slow = slow.nxt
        fast = fast.nxt
    return slow.value

values = [7, 14, 21, 28, 35, 42]
print(values)
print(kth_from_end(build(values), 3))

Key points

Slow pointer: a marker that moves one node at a time.
Fast pointer: a marker that moves ahead first to set the gap.
Use fast and slow pointers to find a node a fixed distance from the end.
Move the fast marker K steps first, then move both markers one step at a time.

The fast marker moves 3 steps first, landing on 28. Both markers then move together until the fast marker runs out. The slow marker lands on 28, which is the 3rd node from the end.

Note

when the fast marker runs out of nodes, the slow marker sits on the answer.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.nxt = nxt

def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
        else:
            tail.nxt = node
        tail = node
    return head

def kth_from_end(head, k):
    fast = head
    for _ in range(k):
        fast = fast.nxt
    slow = head
    while fast is not None:
        slow = slow.nxt
        fast = fast.nxt
    return slow.value

values = [7, 14, 21, 28, 35, 42]
print(values)
print(kth_from_end(build(values), 3))

Exercise

For the 3rd node from the end, how many steps does the fast marker take first?

3 1 2 0