Linked List

Reverse 1→2→3. Save the link to 2 before redirecting 1.next, or the rest becomes unreachable. Draw every arrow change on three nodes before writing assignments.

Three principles hold throughout this article:

1. Every pointer has a meaning you can say in one sentence, such as "prev is the head of the part already reversed", and that sentence is still true after every loop iteration. If you can't say it, don't write the code yet.
2. Before you change an arrow, save the node it currently points to. Once cur.next = ... runs, the rest of the old list is reachable only through a variable you saved beforehand. In the same spirit, always keep hold of the list's entry point (head or dummy).
3. Before you take .next of a variable, be able to say why it isn't None. In Python this bug shows up as AttributeError: 'NoneType' object has no attribute 'next'.

The article goes in this order, and each step adds exactly one idea to the previous one:

When to Use This Pattern

The brute-force approach is to dump the node values into a Python list, solve it on the array, then build a new list. That passes many problems, but it costs O(n) extra space, and interviewers usually follow up with "can you do it in place, with O(1) extra space?"

The trade-off between arrays and linked lists:

A linked list is cheap to restructure (change a few pointers) but can't jump. So the techniques split into two kinds: changing pointers (reverse, delete, merge, reconnect), where the order of assignments matters; and locating a position (middle, n-th from the end, cycle entry), where, since you can't jump, you use the speed or distance gap between two pointers.

Recognition Checklist

• The input is a ListNode head and you must modify in place or use O(1) extra space
• You need to reverse the whole list, a segment of it, or every group of k nodes
• You need the middle, the n-th node from the end, or whether there is a cycle and where it starts
• The head might be deleted or replaced, or you're building a new list from scratch
• You cut the list into pieces, process each, and reconnect them by some rule (reorder, partition, sort)
• A design problem needs O(1) lookup while also maintaining an order of elements

Before You Code

Before writing code, draw the picture and answer these three questions on it:

1. What does each pointer mean, and where does each one stop when the loop ends? For example, "tail is the last node of the result list". Whether the loop stops at cur is None (every node processed) or at cur.next is None (stop on the last node) also follows from what the pointer means.
2. Can the head change? If it might be deleted, moved further back, or the result's head isn't known until the end, put a dummy in front and return dummy.next.
3. Which arrows change in each iteration, and in what order? What must be saved before changing them? Write out the assignments of one iteration in order, and check that before each overwrite of x.next, the node it used to point to is still held by some other variable.

The three answers are connected: question 1 fixes what the pointers mean, question 2 decides where they start (head or dummy), and question 3 writes each iteration's assignments under those meanings.

Try it on LC 21 Merge Two Sorted Lists.

The input is the heads a and b of two lists, each already sorted in nondecreasing order (neighbors may be equal). Merge them into one nondecreasing list and return its head. Reuse the existing nodes; don't copy the values into a Python list and rebuild. Keep every duplicate. Either list, or both, may be empty.

For example, a = 1 → 3 → 5 and b = 2 → 4 → 1 → 2 → 3 → 4 → 5.

• Pointer meanings: a and b are the next not-yet-attached nodes of the two lists; tail is the last node of the result list. The loop stops when a or b reaches None, and the remaining part is attached after tail in one piece.
• Can the head change: the result's head could come from either list, and you don't know which until you compare, so use a dummy and start tail at it.
• Each iteration: compare a and b, attach the smaller one after tail with tail.next = a, then advance a by one and tail by one. What gets overwritten is tail.next, which pointed to tail's successor in its original list. That successor is exactly a or b, which is still held, so nothing is lost.

Step 2 turns this into code.

Reverse Linked List (LeetCode 206)

Given a singly linked-list head, reverse all next links and return the new head, or None for an empty list. The arrow diagram represents node links, not merely rewriting val fields in reverse order.

Input: 1 → 2 → 3 → None. Expected: 3 → 2 → 1 → None.

prev is the head of the part already reversed; cur is the next node to flip; nxt saves the rest of the list.

1. Walk it by hand

2. Read the rule off the table

• Rows 1–3 do the same four moves: save cur.next, point cur back at prev, move prev to cur, move cur to the saved node.
• The save comes first. Once cur.next is changed, the rest of the list is only reachable through nxt.
• When cur is None, every arrow is flipped and prev is the new head.

3. Turn each row into code

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

Core Templates

All five steps follow the same routine: draw the picture and answer the three questions, then check every assignment against the three principles at the top.

Step 1: Three-Pointer Reversal, Save the Rest First

Problem: reverse a singly linked list and return the new head (LC 206).

The input is the list's head head. Turn every node's next around and return the new head. An empty list (head is None) returns None.

For example, 1 → 2 → 3 → 3 → 2 → 1. What changes are the arrows between nodes, not the val fields copied in reverse; the old head becomes the tail, and its next is None.

First, a few small helpers. All the code below uses them to build lists and write asserts:

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


def build(vals):
    # build a linked list from a Python list and return its head
    dummy = tail = ListNode()       # chained assignment: dummy and tail are the same new node
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_list(head):
    # turn a linked list back into a Python list for easy comparison
    out = []
    while head:                     # None is falsy, a node is truthy: same as while head is not None
        out.append(head.val)
        head = head.next
    return out


assert to_list(build([1, 2, 3])) == [1, 2, 3]
assert build([]) is None
assert to_list(None) == []

Two Python idioms here are used throughout. dummy = tail = ListNode() is a chained assignment: it creates one node and binds both names to it. Later tail moves forward while dummy stays put, so dummy.next is still the first real node at the end. In while head:, None counts as false and a node object as true, so it means the same as while head is not None:.

The three questions:

• Pointer meanings: prev is the head of the part already reversed; that part starts out empty, so prev starts as None. cur is the next node to flip. nxt is the head of the part not yet processed. The loop stops when cur becomes None, and then prev is the new head.
• Can the head change: yes, but the new head is just prev at the end, so no dummy is needed.
• Each iteration: only one arrow changes, cur.next = prev. It used to point to the unprocessed part, which nobody else holds, so by principle 2 we first do nxt = cur.next. After the flip, prev and cur each move forward one node and all three meanings hold again.

def reverse_list(head):
    prev, cur = None, head      # parallel assignment: prev = None, cur = head
    while cur:                  # there are still nodes to flip
        nxt = cur.next          # save the rest first
        cur.next = prev         # then flip the arrow
        prev = cur              # move both pointers one step
        cur = nxt
    return prev                 # cur is None; prev is the last node flipped


assert to_list(reverse_list(build([1, 2, 3]))) == [3, 2, 1]
assert to_list(reverse_list(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse_list(build([1]))) == [1]
assert reverse_list(None) is None

prev, cur = None, head is Python's parallel assignment: every value on the right is computed first, then handed to the names on the left in order.

The state at the end of each iteration on 1 → 2 → 3:

Every row satisfies "prev is the head of the reversed part, cur is the head of the unprocessed part". When cur becomes None the loop ends, and prev is 3, the new head.

Here are three ways to get the order wrong:

Step 1 recap

• What it solves: reversing a singly linked list in place, O(n) time and O(1) extra space.
• The key line: nxt = cur.next, which must come before cur.next = prev.
• What the variants change: this step has no variants. Step 4 rewrites it recursively, and LC 92 and LC 25 in Step 5 reverse only part of the list.
• Easiest mistake: flipping the arrow before saving the rest. Reversing [1, 2, 3] leaves only [1]. Make nxt = cur.next the first line of every iteration.

In Step 1 a changing head needs no special handling, because the new head is prev. In deletion and merging problems, you don't know the new head until the end. That's Step 2.

Step 2: If the Head Might Change, Add a Dummy

Problem: merge two sorted lists (LC 21). The statement and the answers to the three questions are in "Before You Code" above.

A dummy is a fake node placed in front of everything. It gives the real first node a predecessor, so "attach the first node" and "attach a later node" become the same line of code. It's useful in two typical situations: the head may be changed during the process, or you're building a new list and don't know yet who will be first. If neither applies, you don't need one.

The three answers are written above; here they are as code:

def merge_two_lists(a, b):
    dummy = tail = ListNode()       # tail: last node of the result list
    while a and b:
        if a.val <= b.val:          # on ties take a first, keeps it stable
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b              # the leftover part is already sorted; attach it whole
    return dummy.next


assert to_list(merge_two_lists(build([1, 3, 5]), build([2, 4]))) == [1, 2, 3, 4, 5]
assert to_list(merge_two_lists(build([1, 2, 4]), build([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert to_list(merge_two_lists(build([]), build([1]))) == [1]
assert to_list(merge_two_lists(build([1, 1]), build([1]))) == [1, 1, 1]
assert merge_two_lists(None, None) is None

a or b gives a if a is not None, and b otherwise. When the loop ends at least one of a and b is None, so this line attaches whichever part is unfinished; if both are finished, it attaches None.

a = 1 → 3 → 5, b = 2 → 4:

Without a dummy you'd compare once before the loop to pick the head, then write the same comparison again inside the loop. The dummy removes that duplicate.

Variation: remove every node equal to val (LC 203)

The input is a list head head and an integer val. Remove every node whose value equals val and return the head of what's left; if everything is removed, return None.

For example, 1 → 2 → 1 with val = 1 → 2: both 1s go, and the new head is the old second node. 7 → 7 → 7 with val = 7 → an empty list. So you can't simply return the original head.

Think first: The head itself may be removed. How can "remove the first node" and "remove a middle node" be the same line of code? After removing a node, should the pointer move forward? Think about two nodes in a row that both need removing.

def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy                        # prev and everything before it are kept
    while prev.next:                    # prev.next is the next node to check
        if prev.next.val == val:
            prev.next = prev.next.next  # delete it; prev does not move
        else:
            prev = prev.next
    return dummy.next


assert to_list(remove_elements(build([1, 2, 1]), 1)) == [2]   # the example from the statement
assert to_list(remove_elements(build([1, 2, 6, 3, 6]), 6)) == [1, 2, 3]
assert to_list(remove_elements(build([7, 7, 7]), 7)) == []
assert to_list(remove_elements(build([1, 7, 7, 2]), 7)) == [1, 2]
assert remove_elements(None, 1) is None

Variation: partition (LC 86)

The input is a list head head and an integer x. Rearrange the nodes into two parts: values less than x first, values greater than or equal to x after. Each part keeps its original relative order; the whole list does not need to be sorted. Return the new head.

For example, 1 → 4 → 3 → 2 → 5 → 2 with x = 3 → 1 → 2 → 2 → 4 → 3 → 5: the values less than 3 are 1, 2, 2, in their original order; the rest are 4, 3, 5, also in order. 3 equals x, so it goes in the second part.

Think first: The result is two lists joined end to end, and neither list's head is known at the start. How many dummies do you need? After you take a node out of the original list and attach it to a new one, what does its old next still point to? Whose next must you fix by hand at the end?

def partition(head, x):
    small = small_tail = ListNode()     # nodes less than x
    large = large_tail = ListNode()     # nodes greater than or equal to x
    cur = head
    while cur:
        if cur.val < x:
            small_tail.next = cur
            small_tail = cur
        else:
            large_tail.next = cur
            large_tail = cur
        cur = cur.next
    large_tail.next = None              # cut the tail: it may still point to a small node
    small_tail.next = large.next        # join the two parts
    return small.next


assert to_list(partition(build([1, 4, 3, 2, 5, 2]), 3)) == [1, 2, 2, 4, 3, 5]
assert to_list(partition(build([2, 1]), 2)) == [1, 2]
assert to_list(partition(build([1, 1]), 5)) == [1, 1]
assert partition(None, 0) is None

One more like it: add two numbers (LC 2)

The input is two nonempty lists l1 and l2, each representing a nonnegative integer: every node holds one decimal digit, least significant digit first. Return the sum in the same format, as a newly built list.

For example, 2 → 4 → 3 is 342 and 5 → 6 → 4 is 465; 342 + 465 = 807, so return 7 → 0 → 8. The lists may have different lengths. If there's a carry out of the top digit, it needs one more node, for example 5 + 5 = 10 → 0 → 1.

Think first: The result list is built from scratch: who is its head, and where do you attach to? When the lists have different lengths, what do you do once the shorter one runs out? Once both have run out, can the loop always stop?

def add_two_numbers(l1, l2):
    dummy = tail = ListNode()
    carry = 0
    while l1 or l2 or carry:            # a leftover carry still needs one more digit
        s = carry
        if l1:
            s += l1.val
            l1 = l1.next
        if l2:
            s += l2.val
            l2 = l2.next
        carry, digit = divmod(s, 10)    # s // 10 and s % 10 at once
        tail.next = ListNode(digit)
        tail = tail.next
    return dummy.next


assert to_list(add_two_numbers(build([2, 4, 3]), build([5, 6, 4]))) == [7, 0, 8]
assert to_list(add_two_numbers(build([9, 9]), build([1]))) == [0, 0, 1]
assert to_list(add_two_numbers(build([0]), build([0]))) == [0]
assert to_list(add_two_numbers(build([5]), build([5]))) == [0, 1]

Step 2 recap

• What it solves: when the head may be removed or replaced, or the result is built from scratch, a dummy gives the first node a predecessor so the head needs no special case.
• The key line: dummy = ListNode(0, head) or dummy = tail = ListNode(), and finally return dummy.next.
• What the variants change: LC 21 uses tail to attach the smaller node; LC 203 switches to prev, which stays put after a deletion; LC 86 builds two lists with two dummies and joins them; LC 2 creates new nodes and adds carry to the loop condition.
• Easiest mistake: forgetting to cut the tail after moving nodes into a new list. Without large_tail.next = None, LC 86 produces a cycle.

So far, one pointer walks from start to end. To find the middle or the n-th from the end, a single pointer doesn't know where to stop. Step 3 adds a second pointer.

Step 3: Fast and Slow Pointers, Locate by Speed or Distance

Problem : return the middle node of a list. The input is a list head. Return the middle node itself (not its value or index). (Pro lesson)

Variation: detect a cycle (LC 141)

The input is a list head head . Decide whether following next forever ever returns to a node already visited . (Pro lesson)

Variation: the cycle's entry (LC 142)

Again a list that may have a cycle. This time, if there is one, return the cycle's entry node : the first node, walking from head, that gets… (Pro lesson)

Variation: remove the n-th node from the end (LC 19)

The input is a nonempty list head head and an integer n . (Pro lesson)

One more like it: find the duplicate number (LC 287)

The input is an integer array nums of length n + 1 whose values are all between 1 and n, so at least one value repeats. (Pro lesson)

Step 3 recap

What it solves : a list can't jump to an index, so use the speed gap (middle, cycles) or distance gap (n-th from the end) between two pointe… (Pro lesson)

Step 4: Recursion, Trust the List the Subproblem Returns

Problem : reverse a list recursively ( LC 206 ). The same problem as Step 1: given a list head, reverse every next and return the new head; (Pro lesson)

One more like it: swap nodes in pairs (LC 24)

The input is a list head. Swap adjacent nodes in pairs: the 1st with the 2nd, the 3rd with the 4th, and so on. Return the new head. (Pro lesson)

Variation: sort a list (LC 148)

The input is a list head. Sort the nodes by value in nondecreasing order and return the new head. Keep every node and every duplicate; (Pro lesson)

Variation: merge k sorted lists (LC 23)

The input is a Python list lists holding the heads of k lists, each nondecreasing. (Pro lesson)

Step 4 recap

What it solves : treat a list as "one node + a shorter list", assume the subproblem is solved, and write only the current level. (Pro lesson)

Step 5: Cut → Process Each Part → Reconnect

This step has no new pointer trick; each part is processed with functions written earlier. (Pro lesson)

One more like it: palindrome linked list (LC 234)

The input is a nonempty list head. Decide whether the node values read the same forwards and backwards, and return True or False. (Pro lesson)

Variation: reverse only nodes left through right (LC 92)

The input is a list head head and two positions left ≤ right , counted from 1 and within the list's length. (Pro lesson)

Variation: reverse nodes in k-groups (LC 25)

The input is a list head and a positive integer k with 1 ≤ k ≤ length . (Pro lesson)

Variation: copy a list with random pointers (LC 138)

Besides next, every node has a random pointer that may point to any node in the list or be None. (Pro lesson)

Step 5 recap

What it solves : break a hard problem into "cut → process each part → reconnect", processing each part with functions written earlier. (Pro lesson)

Advanced: Doubly Linked List + Hash Map (LC 146 LRU Cache)

Problem : implement an LRU (least recently used) cache LRUCache(capacity) with a positive capacity. (Pro lesson)

The Five Steps Side by Side

Step New pointers What they mean Key line Loop stops when Step 1 prev, cur, nxt prev is the head of the reversed part, cur the next node to… (Pro lesson)

One Problem, Many Disguises

Two problems in the table aren't covered in the text, so here are their statements: LC 876 Middle of the Linked List: given a nonempty list,… (Pro lesson)

Common Pitfalls

Flipping the arrow before saving the rest. With cur.next = prev written before nxt = cur.next , reversing [1, 2, 3] leaves only [1] . (Pro lesson)

Say It in the Interview

After confirming whether the input may be modified and whether O(1) extra space is required, you could explain Reorder List ( LC 143 ) like… (Pro lesson)