Linked Lists: Every Pattern You Need, With the Pointer Diagrams Nobody Draws

Linked list problems have a nasty property: a single wrong pointer assignment silently corrupts the entire structure. Unlike arrays where you can index anything, one mistake in a linked list and you've lost everything downstream.

The solution isn't to be more careful. It's to use proven pointer patterns that eliminate the guesswork.

---

The Building Block

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

# Build: 1 -> 2 -> 3 -> 4 -> None
def build(values):
    dummy = ListNode(0)
    curr = dummy
    for v in values:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

# Print for debugging
def to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

---

Pattern 1: The Dummy Head Node

When to use: Any problem where the head itself might be removed or changed — insertion at the front, deletion of the first node, merging lists.

Without dummy head, you have to special-case when the answer starts at head. With it, every node has a previous node.

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head      # dummy -> 1 -> 2 -> 3 -> 4 -> 5
    
    fast = slow = dummy
    
    # Move fast n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both until fast hits end
    while fast:
        fast = fast.next
        slow = slow.next
    
    # slow is now at the node BEFORE the one to delete
    slow.next = slow.next.next
    
    return dummy.next

Why n+1 and not n? We want slow to stop at the node before the target so we can rewire slow.next. The gap of n+1 positions slow one node behind the nth-from-end.

---

Pattern 2: Reversing a Linked List

The most fundamental linked list operation. Every other reversal problem builds on this.

def reverse(head):
    prev = None
    curr = head
    
    while curr:
        next_node = curr.next   # save before overwriting
        curr.next = prev        # reverse the pointer
        prev = curr             # advance prev
        curr = next_node        # advance curr
    
    return prev  # prev is now the new head

Pointer diagram for 1 -> 2 -> 3 -> None:

Initial:  prev=None, curr=1
Step 1:   save next=2, point 1->None, prev=1, curr=2
          None <- 1    2 -> 3 -> None
Step 2:   save next=3, point 2->1, prev=2, curr=3
          None <- 1 <- 2    3 -> None
Step 3:   save next=None, point 3->2, prev=3, curr=None
          None <- 1 <- 2 <- 3
Return prev=3.  Result: 3 -> 2 -> 1 -> None ✓

Reverse a sublist (positions left to right)

def reverse_between(head, left, right):
    dummy = ListNode(0)
    dummy.next = head
    
    # Step 1: reach the node just before position 'left'
    pre = dummy
    for _ in range(left - 1):
        pre = pre.next
    
    # Step 2: reverse from left to right
    curr = pre.next
    for _ in range(right - left):
        next_node = curr.next
        curr.next = next_node.next
        next_node.next = pre.next
        pre.next = next_node
    
    return dummy.next

---

Pattern 3: Two Pointers (Fast and Slow)

Find the middle

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # for even length, returns second middle

Detect cycle (Floyd's algorithm)

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

Find cycle start

def detect_cycle(head):
    slow = fast = head
    
    # Phase 1: find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle
    
    # Phase 2: find cycle start
    # Math: distance from head to cycle start = distance from meeting point to cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

Why phase 2 works: Let F = distance from head to cycle start, C = cycle length, a = distance from cycle start to meeting point. When they meet: slow traveled F + a, fast traveled F + a + kC for some k. Since fast travels 2x: 2(F + a) = F + a + kC, so F = kC - a. Moving a pointer from head and one from meeting point, both travel F steps — they meet at cycle start.

---

Pattern 4: Merge Two Sorted Lists

The merge step you need for merge sort on linked lists, and a standalone interview problem.

def merge_sorted(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    curr.next = l1 or l2   # attach remaining
    return dummy.next

---

Pattern 5: Reorder List

Problem: Given 1 -> 2 -> 3 -> 4 -> 5, reorder to 1 -> 5 -> 2 -> 4 -> 3.

This problem requires three sub-algorithms in sequence — it's a beautiful test of compositional thinking.

def reorder_list(head):
    if not head or not head.next:
        return
    
    # Step 1: Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse second half
    second = slow.next
    slow.next = None   # cut the list in half
    
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    second = prev   # second is now the reversed second half
    
    # Step 3: Merge two halves alternately
    first = head
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

---

Pattern 6: Copy List with Random Pointer

Problem: Each node has a next and a random pointer (can point to any node or None). Deep copy the list.

Naive approach: two passes with a hash map. Optimal: interleave new nodes.

def copy_random_list(head):
    if not head:
        return None
    
    node_map = {}
    
    # First pass: create all new nodes
    curr = head
    while curr:
        node_map[curr] = ListNode(curr.val)
        curr = curr.next
    
    # Second pass: wire next and random pointers
    curr = head
    while curr:
        if curr.next:
            node_map[curr].next = node_map[curr.next]
        if curr.random:
            node_map[curr].random = node_map[curr.random]
        curr = curr.next
    
    return node_map[head]

---

Pattern 7: LRU Cache (Doubly Linked List + Hash Map)

LeetCode #146 is a system design problem disguised as a data structures problem. The solution: a doubly linked list (O(1) move-to-front/remove) combined with a hash map (O(1) lookup).

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key -> Node
        
        # Sentinel head and tail (no edge case handling needed)
        self.head = Node()   # most recently used side
        self.tail = Node()   # least recently used side
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _insert_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    
    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_front(node)   # move to most-recently-used position
        return node.val
    
    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        
        node = Node(key, value)
        self.cache[key] = node
        self._insert_front(node)
        
        if len(self.cache) > self.cap:
            # Remove least recently used (node before tail)
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Why doubly linked list and not singly? Removing a node requires updating its previous node's pointer. With a singly linked list, finding the previous node is O(n). Doubly linked gives you O(1) removal anywhere.

---

Pattern 8: Palindrome Linked List

Check if a linked list is a palindrome in O(n) time, O(1) space.

def is_palindrome(head):
    # Step 1: Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse second half
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt
    
    # Step 3: Compare both halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    
    return True

---

The 5 Rules That Prevent Pointer Bugs

1. Always save next before overwriting. next_node = curr.next before curr.next = something.
2. Use a dummy head when the head itself might change. Saves special-casing.
3. Draw the before/after state. Three boxes, three arrows. Trace one step at a time.
4. Test with lists of length 1, 2, and 3. Edge cases almost always show up here.
5. Check for None before accessing .next. while fast and fast.next — both conditions.

---

Quick Reference: Which Pattern?

| Problem type | Pattern | |---|---| | Head might change | Dummy head | | Find middle | Fast/slow (2:1 speed) | | Detect/find cycle | Fast/slow (Floyd's) | | Remove kth from end | Fast/slow with gap of k | | Reverse entire list | Three-pointer (prev, curr, next) | | Reverse sublist | Four-pointer + dummy head | | Merge two sorted | Two-pointer + dummy head | | Reorder alternately | Find middle + reverse + merge | | Deep copy with random | Hash map (old node → new node) | | O(1) get + put cache | Doubly linked list + hash map |

Practice: Filter Practice by "Linked Lists". Start with Reverse Linked List, then Merge Two Sorted, then Remove Nth from End. Write each from scratch — no auto-complete for the ListNode class.