LeetCode (3): Patterns — Linked List Operations

A linked list is the simplest data structure that forces you to think in pointers. Arrays let you index in $O(1)$ and forget about layout; linked lists hand you a head pointer and ask, “now what?” That single shift — from indices to references — is what makes linked-list problems so common in interviews. They are short to state, brutal to get right, and reward exactly the habits good engineers build: drawing pictures, naming pointers, and never dereferencing without checking for None.

This article covers five problems that, together, encompass every classical linked-list technique you’ll see in coding interviews:

• Reverse a linked list — the canonical pointer-rewiring exercise, both iterative and recursive.
• Merge two sorted lists — the dummy-node pattern and how it eliminates head-case clutter.
• Linked list cycle detection (Floyd) — fast/slow pointers and the algebra that proves they meet at the entrance.
• Remove the nth node from end — two pointers with a fixed gap, in a single pass.
• LRU cache — the doubly linked list + hash map combo that powers every real-world cache.

Each section follows the same format: problem, idea, code, complexity, and a worked example. The figures below show the pointer state before and after each rewiring, which is how you should solve these in your head and on the whiteboard.

Series Navigation#

LeetCode Patterns (10 articles): Hash Tables, Two Pointers, Linked List Operations (this article), Binary Tree Traversal, Dynamic Programming, Backtracking, Binary Search, Stacks and Queues, Graphs, Greedy and Bit Manipulation.

Linked List Fundamentals#

A singly linked list node carries a value and one pointer:

1
2
3
4

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

That is the entire interface. Every algorithm in this article is just a sequence of node.next = something assignments performed in the right order, with the right safety checks.

Linked list vs. array#

The trade-off is clear: arrays excel in access and cache behavior, while linked lists are better for frequent mutations and when you don’t need to jump around. Once you understand this, problem selection becomes obvious — “can I reach the kth element?” suggests an array; “do I need to splice out the middle without copying?” suggests a list.

Insert and delete: rewire two pointers, never more#

Insertion of X between A and B is exactly two assignments, in this order:

1
2

X.next = A.next   # X now points to B
A.next = X        # A now points to X

If you reverse the order, A.next is overwritten before you save it, and B is unreachable. Deletion is even simpler — one assignment redirects A past B, and the garbage collector reclaims B:

1

A.next = B.next   # A skips B

This is the core concept: linked list operations are pointer assignments performed in a specific order. Everything else in this article is a variation on this theme.

LeetCode 206 — Reverse Linked List#

Given the head of a singly linked list, reverse the list and return its new head.

Example: 1 → 2 → 3 → 4 → 5 becomes 5 → 4 → 3 → 2 → 1.

Follow-up: solve it iteratively and recursively.

This is the “hello world” of pointer manipulation. The challenge is that you have to flip every next pointer in place without losing access to the rest of the list.

Iterative: three pointers, $O(1)$ space#

The trick is to remember that flipping curr.next = prev immediately destroys our path forward, so we must save it first.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def reverseList(head):
    """
    Reverse a singly linked list in place.

    Time:  O(n) — every node is visited exactly once.
    Space: O(1) — three pointers, no auxiliary structure.
    """
    prev, curr = None, head
    while curr:
        nxt = curr.next     # 1. save the path forward
        curr.next = prev    # 2. flip the current pointer
        prev = curr         # 3. advance prev
        curr = nxt          # 4. advance curr
    return prev             # prev is the new head (was the tail)

Walkthrough on 1 → 2 → 3 → None:

Return prev = 3, which now heads the reversed list.

Edge cases that the loop already handles correctly:

• Empty list (head is None): the loop body never runs, return prev = None.
• Single node: one iteration, sets 1.next = None, returns 1.

Recursive: rewire on the way back up#

The recursive view says: “reverse everything after head, then make the old head.next point back to head.”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def reverseList_recursive(head):
    """
    Reverse a linked list recursively.

    Time:  O(n).
    Space: O(n) — recursion stack.
    """
    if not head or not head.next:
        return head

    new_head = reverseList_recursive(head.next)

    # head.next is the tail of the already-reversed sublist.
    # Make it point back to head, then sever head's outgoing link.
    head.next.next = head
    head.next = None
    return new_head

The single line that confuses everyone is head.next.next = head. Read it slowly:

• head.next is the node that comes right after head in the original list.
• After the recursive call, that node has become the tail of the reversed sublist.
• We want the tail to point back to head, so we assign to head.next.next.

Then head.next = None cuts head’s outgoing link so the new tail terminates cleanly.

Iterative or recursive?#

In an interview, lead with iterative. Mention recursive as a follow-up to show range. In production, always pick iterative — Python’s default recursion limit (1000) will bite you on long lists.

LeetCode 21 — Merge Two Sorted Lists#

Merge two sorted linked lists into one sorted list by splicing existing nodes.

Example: l1 = [1,2,4], l2 = [1,3,4] → [1,1,2,3,4,4].

The interesting question here is not the merge — that is just standard two-pointer comparison — but how to handle the first node of the result. Without a helper, you need a special branch to decide which list contributes the head. With a dummy node, that branch disappears.

Iterative with a dummy node#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def mergeTwoLists(l1, l2):
    """
    Merge two sorted lists by splicing nodes (no allocation).

    Time:  O(m + n) — each input node is visited once.
    Space: O(1) — only the dummy node and a cursor.
    """
    dummy = ListNode()    # sentinel; never returned
    cur = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    # At most one list still has nodes; attach it whole.
    cur.next = l1 if l1 else l2

    return dummy.next

Why the dummy? It guarantees there is always a “previous node” to write to. Without it, the first iteration would need to decide whether the head is from l1 or l2, which forks every subsequent branch. With the dummy, every iteration looks the same — the head case has been smuggled into the sentinel.

Walkthrough on l1 = [1,2,4], l2 = [1,3,4]:

Return dummy.next.

Recursive variant#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def mergeTwoLists_recursive(l1, l2):
    """
    Recursive merge. Elegant but uses O(m + n) stack.

    Time:  O(m + n).
    Space: O(m + n) — recursion depth equals total length.
    """
    if not l1: return l2
    if not l2: return l1
    if l1.val <= l2.val:
        l1.next = mergeTwoLists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists_recursive(l1, l2.next)
        return l2

LeetCode 141 / 142 — Linked List Cycle (and where it begins)#

141: Detect whether a linked list has a cycle.

142: Return the node where the cycle begins, or None if there is no cycle.

Constraint: $O(1)$ extra space.

The brute-force solutions — hash every node, or count steps — are correct but use $O(n)$ space or two passes. Floyd’s tortoise-and-hare algorithm does it in one pass with two pointers and a small piece of algebra.

Phase 1: detect the cycle#

1
2
3
4
5
6
7
8
9

def hasCycle(head):
    """LeetCode 141. Detect a cycle using fast/slow pointers."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next         # 1 step
        fast = fast.next.next    # 2 steps
        if slow is fast:
            return True
    return False

Why does it work? If there is no cycle, fast reaches None and the loop exits. If there is a cycle, both pointers are eventually trapped inside it, and because fast gains one node per step on slow, the gap shrinks by 1 per iteration and they must collide within at most $L$ iterations (where $L$ is the cycle length).

Phase 2: locate the cycle entrance#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def detectCycle(head):
    """
    LeetCode 142. Return the node where the cycle begins.

    Time:  O(n). Space: O(1).
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Phase 2: reset slow, advance both by 1 step.
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

The algebra (worth memorizing once)#

Let $a$ = distance from head to the entrance, $b$ = distance from the entrance to the meeting point along the cycle, $c$ = the rest of the cycle (so cycle length $L = b + c$ ).

That last equality is the punchline. It says: walking $a$ steps from the head lands on the entrance, and walking $a$ steps from the meeting point also lands on the entrance (because $(k-1)L$ is just whole loops). So if we reset slow to head and step both pointers one node at a time, they meet at the entrance.

LeetCode 19 — Remove Nth Node From End#

Given the head of a linked list, remove the nth node from the end and return the head. Try to do it in one pass.

Example: head = [1,2,3,4,5], n = 2 → [1,2,3,5].

The naïve approach takes two passes: count the length, then walk to position length - n. The one-pass solution uses two pointers separated by a fixed gap of $n + 1$ , plus a dummy node so deleting the head requires no special case.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def removeNthFromEnd(head, n):
    """
    Remove the nth node from end in a single pass.

    Time:  O(L) where L is the list length.
    Space: O(1).
    """
    dummy = ListNode(0, head)    # handles deletion of the head uniformly
    slow = fast = dummy

    # Move fast n+1 steps ahead so that when fast hits None,
    # slow sits on the node BEFORE the one we want to remove.
    for _ in range(n + 1):
        fast = fast.next

    while fast:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return dummy.next

Why $n+1$ , not $n$ ? We need slow to land on the predecessor of the target so we can rewire slow.next. If fast only moves $n$ steps, the gap between them is $n$ , so when fast is None, slow is on the target, not before it. Off by one is the single most common bug here.

Why the dummy? Consider head = [1, 2], n = 2 (delete the head). With the dummy:

• fast moves 3 steps, ending at None.
• slow is still at dummy.
• dummy.next = dummy.next.next sets dummy.next = 2.
• Return dummy.next = 2. Done.

Without the dummy, you would need a separate branch like if n == length: return head.next, which means computing the length first — and now you have a two-pass solution again.

LeetCode 146 — LRU Cache#

Design a data structure with get(key) and put(key, value) that both run in $O(1)$ amortized time. When capacity is exceeded, evict the least recently used key.

This problem comes up everywhere — operating system page caches, CDN edge caches, browser caches, your ORM’s query cache. The standard solution is a small but beautiful composition: a hash map for $O(1)$ lookup, plus a doubly linked list for $O(1)$ reordering and eviction.

Why both data structures?#

• A hash map alone gets us $O(1)$ lookup but no notion of recency.
• A linked list alone tracks recency but lookup is $O(n)$ .
• Together: lookup the node in the map ($O(1)$ ), then unlink and re-link it at the head of the list ($O(1)$ because it is doubly linked).

The list maintains the ordering “most recently used at the head, least recently used at the tail”. Two sentinel nodes (head and tail) eliminate every edge case for inserting at the front or evicting from the back.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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

class LRUCache:
    """
    O(1) get and put using hash map + doubly linked list with sentinels.

    Invariant:
        head <-> most recent <-> ... <-> least recent <-> tail
    """

    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                       # key -> Node
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    # ----- list primitives -----

    def _remove(self, node: "Node") -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: "Node") -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    # ----- public API -----

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_to_front(node)            # mark as most recent
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return

        if len(self.map) >= self.cap:
            lru = self.tail.prev            # least recently used
            self._remove(lru)
            del self.map[lru.key]

        new_node = Node(key, value)
        self.map[key] = new_node
        self._add_to_front(new_node)

Three things worth pausing on:

1. Sentinels are not optional. They turn every insertion and removal into the same four-pointer dance, with no if head is None checks anywhere.
2. The node carries the key. When we evict the LRU node, we need to delete its key from the map — without storing the key on the node, we would have to walk the map to find it.
3. We splice existing nodes; we never re-allocate on get. That is what gives us true $O(1)$ amortized cost.

Pattern Cheat Sheet#

Common Pitfalls#

1. Dereferencing without checking. curr.next.val crashes the moment curr.next is None. Always guard: while curr and curr.next:.
2. Losing the path forward. Before writing curr.next = something, save the original curr.next if you still need it (this is the entire point of the nxt variable in iterative reverse).
3. Forgetting to advance. Every loop iteration must move at least one pointer toward termination, or you have an infinite loop.
4. Off-by-one on gaps. Two-pointer gap problems live and die on whether you advance fast by n or n + 1 first.
5. Skipping the dummy node. Anytime the head can change, a dummy will collapse 5 lines of edge-case branching into 0.

Exercises#

Sorted roughly by difficulty within each group.

Basics

• LeetCode 206 — Reverse Linked List (covered)
• LeetCode 21 — Merge Two Sorted Lists (covered)
• LeetCode 19 — Remove Nth Node From End (covered)
• LeetCode 234 — Palindrome Linked List

Cycles and intersection

• LeetCode 141 — Linked List Cycle (covered)
• LeetCode 142 — Linked List Cycle II (covered)
• LeetCode 160 — Intersection of Two Linked Lists

Advanced

• LeetCode 25 — Reverse Nodes in k-Group
• LeetCode 23 — Merge K Sorted Lists
• LeetCode 138 — Copy List with Random Pointer
• LeetCode 146 — LRU Cache (covered)
• LeetCode 460 — LFU Cache

References#

• Introduction to Algorithms — the Elementary Data Structures chapter.
• Cracking the Coding Interview — Chapter 2 , Linked Lists.
• VisuAlgo — Linked List visualization: https://visualgo.net/en/list ↗
• LeetCode Linked List tag — 100+ curated problems for practice.

Where Linked Lists Actually Live in Production#

Most application code never touches ListNode directly — the language’s standard library hides it. But the structure is everywhere underneath:

• LRU caches. functools.lru_cache, Redis’s allkeys-lru eviction, every browser’s HTTP cache. They’re all hash-map + doubly-linked-list, exactly like LeetCode 146. Knowing why (O(1) move-to-front requires a node pointer, which a Python list doesn’t give you) is what the interview question actually probes.
• Linux kernel lists. include/linux/list.h defines an intrusive doubly-linked list used by tens of thousands of kernel structures — process lists, file descriptor tables, network queues. The “container_of” trick that makes intrusive lists work is one of the most elegant pieces of C in the kernel.
• Java’s LinkedHashMap and Python’s OrderedDict. Insertion-order iteration is implemented as a hash map plus a linked list of entries. Same structure, different language.
• Skip lists in Redis sorted sets. A multi-level linked list with probabilistic shortcuts. Used because they’re easier to make lock-free than balanced trees.

The point: linked-list problems aren’t “exercises.” They are the smallest examples of patterns you’ll meet again at every layer of the stack.

Cleaner Python Idioms#

The default LeetCode style is C-with-Python-syntax. A few changes make the code easier to write and to read:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# Iterate the list with a generator.
def to_list(head):
    while head:
        yield head.val
        head = head.next

# Compare two lists by content (great in tests).
assert list(to_list(result)) == [1, 2, 3, 4]

# Build a list from a Python iterable (great for setup).
def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

These three helpers turn link-list testing from “manually trace pointers” into one-liners. I keep them at the top of every linked-list file.

For reverse, the recursive form is shorter than the iterative form and it teaches the structure. Use it once you trust the stack depth:

1
2
3
4
5
6
7

def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

The line head.next.next = head is the entire algorithm — read it as “the node after me should now point back to me.”

A Common Bug: Mutating While Traversing#

Two-pointer linked-list code looks like array code, but the consequences of a mistake are different. The single most common bug:

1
2
3
4
5

# WRONG — modifies curr.next before saving the next pointer
curr = head
while curr:
    curr.next = something_new   # we just lost the rest of the list
    curr = curr.next            # this now follows the new pointer

The fix is religious: save the next pointer before any assignment that touches .next:

1
2
3
4
5

curr = head
while curr:
    nxt = curr.next             # save first
    curr.next = something_new
    curr = nxt                  # then advance via the saved pointer

Every iterative linked-list algorithm follows this pattern. If your code skips a node, lands in an infinite loop, or “loses half the list,” nine times out of ten it’s because some assignment ran before the save.

Test Battery for Linked-List Code#

Before submitting, run mentally:

Five seconds per row, thirty-five seconds total — saves the wrong-answer slog.

Summary#

Linked-list problems are not really about linked lists. They are about being precise with mutation — naming the pointers, ordering the assignments, and never assuming the next field is non-null. The five problems above cover every technique you need: pointer rewiring, dummy nodes, fast/slow traversal, gap pointers, and the hash-map + list combination.

Once you can write reverseList from memory and explain why Floyd’s algorithm works on a napkin, the rest of the linked-list canon falls out as variations on those themes. In the next article we move from one-dimensional pointer chains to binary trees, where recursion finally feels like the natural tool instead of a clever trick.