Know this before you start: “Fast & slow pointers for middle / cycle”

Fast and slow pointers on a linked list

Move one pointer two steps and another one step. When fast reaches the end, slow is in the middle; if there's a loop, they meet inside it.

The idea

Two pointers at different speeds reveal a list's shape with no extra memory. FAST moves two nodes per step, SLOW moves one.

If the list ends, FAST gets there first, and SLOW has gone half as far: the middle. If the list loops, FAST eventually laps SLOW and they land on the same node.

See it step by step

Middle of 1 → 2 → 3 → 4 → 5

slow 1, fast 1 → slow 2, fast 3 → slow 3, fast 5
fast can't move two more → the middle is 3.

In code (Python)

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

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

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

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for a, b in zip(nodes, nodes[1:]):
    a.next = b
print(middle(nodes[0]).val, has_cycle(nodes[0]))   # 3 False
nodes[-1].next = nodes[1]
print(has_cycle(nodes[0]))                          # True

O(n) time, O(1) space.

When you'll use it

Middle node, cycle detection, where a cycle starts, palindrome lists, “find the duplicate number”.

Common mistakes

Checking fast.next.next before fast.next exists.
Comparing values instead of the nodes themselves.