Linked Lists

The shape and the trade-off

A node holds a value and a reference to the next node; you can’t index in — you walk. Versus an array:

So linked lists shine when you splice in the middle a lot and don’t need random access (queues, LRU caches, adjacency lists). The skill is rewiring next pointers without losing the rest of the list.

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

Reversal (the canonical move)

Flip each pointer as you walk; keep three references so you never lose the tail:

def reverse_list(head):
    prev = None
    while head:
        nxt = head.next      # save the rest
        head.next = prev     # flip
        prev = head          # advance both
        head = nxt
    return prev              # new head

Recursive variant reverses the tail then points head.next.next = head. Reversing a sublist (positions m..n) is the same move bounded by saved boundary pointers.

Fast & slow pointers (Floyd’s)

Advancing one pointer twice as fast as the other, in O(1) space:

• Find the middle — slow lands at the midpoint when fast hits the end.
• Detect a cycle — fast laps slow inside a loop:

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

• Find the cycle’s start — after they meet, move one pointer to the head and advance both at the same speed; they meet at the entry. (The math: meeting point distance equals head-to-entry distance modulo the loop length.)
• Nth node from the end — advance one pointer n steps first, then move both until it hits the end; the trailing pointer is at the target (a two-pointer “gap”).

The dummy head trick

When the head itself might change (merging, deleting the first node), allocate a throwaway node before the head so every node — including the real first — is handled uniformly; return dummy.next:

def merge_two(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next
        else:              tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b      # attach the remainder
    return dummy.next

This powers Merge Two Sorted Lists, Remove Nth From End, Reorder List, and Add Two Numbers.

Merging k lists

Combine k sorted lists by either a min-heap over the k current heads (O(N log k)) or divide-and-conquer pairwise merging (also O(N log k)) — see the heaps and divide-and-conquer primers.

Doubly linked lists and the LRU cache

A doubly linked list (prev + next pointers) allows O(1) removal of a known node from the middle. Paired with a hash map (key → node), it gives the LRU cache: move-to-front on access, evict the tail — every operation O(1). This combo (hash map + DLL) is the single most common “design” problem; know it cold.

Recursion on lists

Many list problems read cleanly as recursion (reverse, merge, swap pairs, add two numbers) — the base case is the empty/last node. Watch the O(n) call-stack depth on long lists; an iterative version is the safe default when depth is a concern.

Common pitfalls

• Losing the rest of the list — save head.next before you overwrite it.
• Null dereference — guard while fast and fast.next and check before node.next.next.
• Forgetting to terminate — set the final node’s next = None (e.g. after partitioning, or it can create a cycle).
• Edge cases — empty list, single node, even vs odd length (which middle?), the head changing.

Choosing in an interview

• Reverse / reorder / splice → pointer rewiring with three saved references.
• Middle / cycle / nth-from-end → fast & slow pointers (O(1) space).
• Head might change → dummy node.
• Merge sorted → dummy node (two) or heap / divide-and-conquer (k).
• O(1) middle removal / cache → doubly linked list + hash map.

Draw the pointers before you code — a quick diagram of “before/after rewire” prevents almost every linked-list bug.