Pattern 14 of 27

Linked List Manipulation

Rewire next pointers carefully, using a dummy head and saved references so no node is lost while the list changes shape.

Cost: O(n) time, O(1) extra space for most rewiring
Problems: 6

When to reach for it

The input is a linked list and the output is the same nodes in a new order.
The prompt says reverse, merge, swap, or copy.
The head of the list itself might change.

How it works

Linked list problems are rarely hard algorithms; they are mostly about never losing a reference. Before changing node.next, save the node it pointed to. A dummy node in front of the head removes the special case where the first node changes. Reversing any section follows the same three moves every time: save next, point the current node backwards, advance. Drawing four nodes and their arrows on paper catches almost every bug before the code runs.

The template

Written for Merge Two Sorted Lists (write-up)

def merge_two_lists(a, b):
    dummy = tail = ListNode(0)        # dummy head: no special case for the first node
    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
    return dummy.next

Open in the editor Trace it line by line

Six problems, in learning order

1.Merge Two Sorted ListsLeetCode 21A dummy head, attaching the smaller node at each step.Easy
2.Merge k Sorted ListsLeetCode 23Merge k lists with a min-heap of the current heads, or by merging pairs repeatedly.Hard
3.Swap Nodes in PairsLeetCode 24Swap each pair by rewiring three pointers from a dummy node.Medium
4.Reverse Nodes in k-GroupLeetCode 25Reverse k nodes at a time, but only when k nodes remain.Not in the curated 370 yet.Hard
5.Reverse Linked List IILeetCode 92Walk to the node before left, then reverse exactly right - left + 1 nodes.Medium
6.Copy List with Random PointerLeetCode 138Map each original node to its copy, or weave the copies into the list itself.Medium

What usually goes wrong

Overwriting node.next before saving it, which cuts off the rest of the list.
Returning head instead of dummy.next after the head has moved.
Leaving a cycle behind by not setting the new tail's next to None.