Linked List Pattern: Template + 75 LeetCode Problems

What the linked list pattern is

Linked list problems are pointer-rewiring exercises, and nearly all of the difficulty is in the edge cases rather than the algorithm. Two habits remove most of them. First, allocate a dummy node in front of the real head whenever the head itself might be deleted or replaced, so the head stops being a special case and the answer is always `dummy.next`. Second, before overwriting any `next`, save it — the reversal loop is exactly the three-step dance of saving the successor, redirecting the current node backwards, and stepping both cursors forward. The other half of the pattern is fast-and-slow pointers: advancing one cursor two nodes for every one of the other's finds the midpoint in a single pass, detects a cycle when the two meet, and locates the cycle's entry point when a third walk starts from the head. In-place work keeps the space at O(1), which is usually the actual constraint being tested.

When to use it

• —Nodes must be reordered, reversed, merged or removed without allocating a new list.
• —The head of the list can change — that is the dummy node's cue.
• —A cycle, a midpoint, or the nth node from the end is wanted in one pass.
• —The problem forbids converting the list to an array, which is otherwise always tempting.

The linked list template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 75 problems listed below.

def reverse(head):
    previous = None
    node = head

    while node:
        following = node.next    # save it before the link is destroyed
        node.next = previous     # rewire backwards
        previous = node          # step both cursors forward
        node = following

    return previous              # the old tail is the new head

Complexity characteristics

Time

O(n)

Auxiliary space

O(1)

One pass, rewiring pointers as it goes. The constant space is the entire point of the pattern and is usually the constraint being tested — copying the list into an array makes almost all of these problems trivial at O(n) space, which is why the statement so often forbids it. Fast-and-slow pointers hold both figures: the midpoint, a cycle check and the nth node from the end each cost one pass and two pointers.

All 75 linked list LeetCode problems

Every problem in the library the linked list pattern applies to, grouped by LeetCode's own difficulty rating. 63 of the 75 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Linked List pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.