Fast and Slow Pointers

Two speeds through a list

Moving one pointer one step and another two steps finds the middle (when fast reaches the end, slow is halfway) and detects cycles (Floyd's algorithm: in a cycle, fast eventually meets slow) in O(1) extra space. Reversing a list in place re-points each next to the previous node. Draw the pointers before coding; most bugs are lost references.

Pointers and recursion

Linked lists reward careful pointer handling; trees reward recursive thinking and level-by-level traversal.

Middle, cycle detection and reversal, run

I ran this with Python 3.12.3 (standard library only). Odd and even lengths give middles 3 and 4 (the second middle); linking node 4 back to node 2 creates a cycle that is detected; reversal returns 3, 2, 1.

# Fast and slow pointers on a linked list
class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

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

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

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

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

print(middle(build([1, 2, 3, 4, 5])), middle(build([1, 2, 3, 4, 5, 6])))
lst = build([1, 2, 3, 4])
print(has_cycle(lst))
lst.next.next.next.next = lst.next       # 4 -> 2 creates a cycle
print(has_cycle(lst))
r, out = reverse(build([1, 2, 3])), []
while r:
    out.append(r.val); r = r.next
print(out)

Output:

3 4
False
True
[3, 2, 1]

Use a dummy head

A dummy node before the head simplifies insertions and deletions at the front.

Quick check: How does Floyd's algorithm detect a cycle?

• By storing every node in a list
• A fast pointer moving two steps eventually meets a slow pointer moving one step
• By sorting the list
• By counting to a fixed limit