AI Hints
Home›DSA in Python Tutorial›Linked List Techniques
DSA in Python · Lesson 38 of 132

Fast and Slow Pointers

The tortoise and the hare.

⏱ 2 min read▶ Video at 44:03🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Send two pointers along a linked list. The slow one moves one step at a time, and the fast one moves two. That simple idea finds the middle of a list, and detects loops, without any extra memory.

Fast and Slow Pointers
From the video: Fast and Slow Pointers
  • Slow moves one step
  • Fast moves two
  • Middles and loops

Finding the middle

When the fast pointer reaches the end, the slow pointer has gone exactly half as far. So it's standing on the middle node. Run it. The middle of one to five is three. For one to six, it's four, the second of the two middle nodes.

middle.pypython
from node import build

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.value

print(middle(build([1, 2, 3, 4, 5])))
print(middle(build([1, 2, 3, 4, 5, 6])))
Output
3
4
Also uses node.py
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def show(head):
    vals = []
    while head:
        vals.append(str(head.value))
        head = head.next
    print(" -> ".join(vals) + " -> None")

Detecting a loop

A broken list might loop back on itself, so walking it would never end. With a loop, the fast pointer eventually laps the slow one, like a faster runner on a track. If they ever meet, there's a loop. If fast reaches the end, there isn't. Run it.

cycle.pypython
from node import build

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

head = build([1, 2, 3, 4])
print(has_cycle(head))
head.next.next.next.next = head.next
print(has_cycle(head))
Output
False
True
Also uses node.py
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def show(head):
    vals = []
    while head:
        vals.append(str(head.value))
        head = head.next
    print(" -> ".join(vals) + " -> None")

Summary

Slow and fast pointers find the middle, and detect loops, in O of N time with O of one memory. Next, linked lists with arrows in both directions.

Key takeaways
  • slow: 1 step, fast: 2
  • Middle: where slow stops
  • They meet: a loop
Next up: Doubly Linked Lists — arrows both ways