Common Linked List Patterns

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 2 Time to complete: ~30 minutes

Reversing a Linked List — Iterative
Reversing a Linked List — Recursive
Fast/Slow Pointers: Finding the Middle
Fast/Slow Pointers: Cycle Detection (Floyd's Algorithm)
Merging Two Sorted Linked Lists
Summary & Next Steps

1. Reversing a Linked List — Iterative

Reversal means flipping every next pointer to point backward. It's done in a single pass using three tracking variables:

def reverse_iterative(head):
    previous = None
    current = head
    while current is not None:
        next_node = current.next     # save it before we overwrite current.next
        current.next = previous       # flip the pointer
        previous = current
        current = next_node
    return previous                    # previous is now the new head
    # O(n) time, O(1) auxiliary space

Trace through [1, 2, 3]: after each iteration, previous chains one more node backward — by the end, previous points to what used to be the tail (3), now leading 3 → 2 → 1 → None.

2. Reversing a Linked List — Recursive

def reverse_recursive(head):
    if head is None or head.next is None:
        return head                    # base case: empty list or single node
 
    new_head = reverse_recursive(head.next)   # reverse everything after `head`
    head.next.next = head                       # make the next node point back to head
    head.next = None                              # head is now the tail
    return new_head
    # O(n) time — one call per node
    # O(n) space — the call stack itself (Module 1, Chapter 4)

Same time complexity as the iterative version, but O(n) space instead of O(1) because of the recursion call stack — a direct application of Module 1 Chapter 4's point that recursion has a real space cost even without an explicit data structure.

3. Fast/Slow Pointers: Finding the Middle

Two pointers start at the head; fast moves two steps for every one step of slow. When fast reaches the end, slow is at the middle:

def find_middle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow
    # O(n) time, O(1) space — one pass, no extra structure

This avoids the two-pass alternative (count the length, then walk length // 2 steps) — fast/slow does it in a single pass.

4. Fast/Slow Pointers: Cycle Detection (Floyd's Algorithm)

The same fast/slow setup detects whether a linked list loops back on itself (a "cycle") instead of ending in None:

def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:               # they've met — must be a cycle
            return True
    return False
    # O(n) time, O(1) space

Why this works: if there's no cycle, fast reaches None and the loop ends normally. If there is a cycle, both pointers eventually enter it and never leave. Once inside, fast gains on slow by exactly one node per iteration (it moves 2 steps to slow's 1) — so the gap between them shrinks by one each time. A shrinking gap on a loop must eventually hit zero, meaning fast laps slow and they land on the same node. This is why it's also called the "tortoise and hare" algorithm, and it detects a cycle using only O(1) extra memory — no need to store every visited node in a set (which would also work, but at O(n) space).

5. Merging Two Sorted Linked Lists

Given two already-sorted lists, produce one sorted list by re-linking nodes (no new nodes created):

def merge_sorted(head_a, head_b):
    dummy = Node(None)          # a placeholder to simplify edge cases
    tail = dummy
 
    while head_a is not None and head_b is not None:
        if head_a.value <= head_b.value:
            tail.next = head_a
            head_a = head_a.next
        else:
            tail.next = head_b
            head_b = head_b.next
        tail = tail.next
 
    tail.next = head_a if head_a is not None else head_b   # attach whatever's left
 
    return dummy.next            # skip past the dummy placeholder
    # O(n + m) time — one pass through both lists combined
    # O(1) auxiliary space — reuses existing nodes, no new ones allocated

The dummy node is a common trick: it sidesteps special-casing "what if the merged list is empty at the start" — you always have somewhere to attach the first real node, then discard the dummy at the end. This pattern reappears directly in merge sort's merge step (Module 3, Chapter 4).

6. Summary & Next Steps

Key Takeaways

Reversal can be done iteratively (O(1) space) or recursively (O(n) space from the call stack) — same time complexity, different space tradeoff.
Fast/slow pointers solve both "find the middle" and "detect a cycle" in a single pass with O(1) space — a much better space profile than a two-pass or hash-set-based approach.
The dummy-node trick simplifies merge logic by removing head-of-list special cases.

Concept Check

Why does the recursive reversal use O(n) space while the iterative version uses O(1)?
Explain, in your own words, why the fast pointer is guaranteed to catch the slow pointer if a cycle exists.
What role does the dummy node play in merge_sorted, and what would break without it?

Next Chapter

→ Chapter 4: Practice Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index