Linked Lists: Traversal, Reversal & Fast/Slow Pointers

Why Linked Lists Need Their Own Mental Model

Arrays give you O(1) random access because the whole block sits in one contiguous chunk of memory. A singly linked list trades that away on purpose: each node holds a value and a pointer to the next node, scattered anywhere in memory. You can't jump to index k in O(1) — you have to walk k pointers to get there. What you get back: O(1) insertion/deletion at a known position, no resizing, and a data structure that's the backbone of hash-table chaining, LRU caches, and every "reverse this in-place" interview question.

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

Traversal

def to_list(head: ListNode) -> list:
    out = []
    node = head
    while node:
        out.append(node.val)
        node = node.next
    return out

O(N) time, O(1) extra space beyond the output. The habit that matters: always advance with node = node.next inside the loop — forgetting it is the #1 way to write an infinite loop on a list with a cycle.

Iterative Reversal — the pattern that shows up everywhere

def reverse_list(head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr:
        nxt = curr.next      # save before you overwrite it
        curr.next = prev     # rewire backward
        prev, curr = curr, nxt
    return prev               # prev is the new head

The line that trips people up: you must save curr.next in a temp variable before reassigning curr.next = prev — otherwise you lose the rest of the list the moment you rewire the current node. O(N) time, O(1) space.

Recursive version (same result, O(N) call-stack space instead of O(1)):

def reverse_list_recursive(head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Fast/Slow Pointers (Floyd's Algorithm)

Find the middle: move slow one step and fast two steps per iteration; when fast reaches the end, slow is at the middle.

def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Detect a cycle: if fast ever equals slow, there's a cycle. Why they must meet: every step, the gap between them shrinks by exactly 1 once both are inside the cycle, so it can never "jump over" — it always lands on slow eventually.

def has_cycle(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Find where the cycle starts: once slow and fast meet, reset one pointer to head and advance both one step at a time — they meet again exactly at the cycle's start. This falls out of the same distance algebra that proves they meet at all.

def detect_cycle_start(head: ListNode):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            ptr = head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None

Merge Two Sorted Lists

def merge_two_sorted(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2
    return dummy.next

The dummy head trick removes every "is this the first node?" special case — you always have a tail to hang the next node off of, even before you've picked a real head.

Common Mistakes

1. Losing the rest of the list during reversal by rewiring curr.next before saving it.
2. Off-by-one in fast/slow: advancing fast before checking fast.next is not None causes a crash on even-length lists.
3. Treating slow is fast (identity) and slow.val == fast.val (value equality) as the same check for cycle detection — only identity is correct, since two different nodes can hold the same value.
4. Forgetting the dummy-head trick and hand-writing "if head is None, set it to this node, else append" branches in merge code.

Takeaway

Every linked-list interview question combines four moves: traverse, reverse, fast/slow-pointer, and merge-with-a-dummy-head. Recognize which combination a problem needs before you start coding — Mock 2 tests exactly these four, back to back.