Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Reversing a Linked List

Editorial

Turning the line around

Picture a line of people, each pointing at the person in front of them. To turn the line around, everyone has to point at the person behind instead. Nobody moves; only the pointing changes. The one rule: you can't stop pointing forward until someone else is holding on to the people ahead of you, or they wander off.

Reversing a linked list is that. Every next pointer turns around, the old tail becomes the head, and no node moves or gets copied. It's one of the most asked list questions, and it's a step inside Palindrome Linked List, Reorder List and Reverse Nodes in k-Group.

The first answer most people find copies the values out and writes them back in reverse:

def reverse_by_copy(head):
    values = []
    curr = head
    while curr is not None:             # one pass to copy every value out...
        values.append(curr.val)
        curr = curr.next
    curr = head
    while curr is not None:             # ...and one to write them back, last first
        curr.val = values.pop()
        curr = curr.next
    return head

It returned 5 -> 4 -> 3 -> 2 -> 1 -> null for 1 → 2 → 3 → 4 → 5. It's correct, but it needs an array as long as the list, O(n) extra space, and it rewrites values instead of links, which an interviewer will ask you to avoid. Turning the pointers needs three variables, whatever the length.

The list 1 to 5 before and after one step of the reversal. Before: the reversed part, null ← 1 ← 2, held by prev, then a dashed boundary, then the part not touched yet, 3 → 4 → 5 → null, held by curr. A strip of three numbered writes: next = curr.next, curr.next = prev, then prev = curr and curr = next. After: null ← 1 ← 2 ← 3 with the new link in green, the boundary one node further right, and curr on 4. A focal line reads: 1 node crosses per step, O(1) extra space.

Two lists, one node at a time

Think of the list as two lists at every moment. prev heads the part already reversed, which ends in null. curr heads the part not touched yet. Every node is in exactly one of them. One step takes curr's node and moves it to the front of prev's list:

  1. save curr.next, the rest of the untouched part;
  2. point curr back at prev;
  3. move prev to curr, and curr to the saved node.

When curr is null, the untouched part is empty, so prev heads the whole list, reversed. Each node is handled once: O(n) time, O(1) extra space.

Reverse the whole list — Teal nodes are the reversed part that prev heads; curr is indigo. The green arrow is the pointer just turned around.

Node* reverse(Node* head) {
    Node* prev = nullptr;                // heads the part already reversed
    Node* curr = head;                   // heads the part not touched yet
    while (curr != nullptr) {
        Node* next = curr->next;         // 1. save the rest
        curr->next = prev;               // 2. point back
        prev = curr;                     // 3. move both on
        curr = next;
    }
    return prev;                         // the old tail, now the head
}

def reverse(head):
    prev = None                         # heads the part already reversed
    curr = head                         # heads the part not touched yet
    while curr is not None:
        nxt = curr.next                 # 1. save the rest
        curr.next = prev                # 2. point back
        prev = curr                     # 3. move both on
        curr = nxt
    return prev                         # the old tail, now the head

static Node reverse(Node head) {
    Node prev = null;                    // heads the part already reversed
    Node curr = head;                    // heads the part not touched yet
    while (curr != null) {
        Node next = curr.next;           // 1. save the rest
        curr.next = prev;                // 2. point back
        prev = curr;                     // 3. move both on
        curr = next;
    }
    return prev;                         // the old tail, now the head
}

function reverse(head) {
    let prev = null;                     // heads the part already reversed
    let curr = head;                     // heads the part not touched yet
    while (curr !== null) {
        const next = curr.next;          // 1. save the rest
        curr.next = prev;                // 2. point back
        prev = curr;                     // 3. move both on
        curr = next;
    }
    return prev;                         // the old tail, now the head
}

Each printed 5 -> 4 -> 3 -> 2 -> 1 -> null for 1 to 5, 7 -> null for one node, and null for an empty list: the loop never runs and prev is still null.

Why the save comes first, and why the answer is prev

Before the flip, curr.next is the only pointer to the rest of the untouched part. Flip first and the rest is gone before you read it:

def reverse(head):
    prev, curr = None, head
    while curr is not None:
        curr.next = prev                # the rest is gone before it's read
        prev, curr = curr, curr.next
    return prev

On 1 → 2 → 3 → 4 → 5 this returned 1 -> null. curr.next was already null when the loop read it, so the loop stopped after one node, and 2 to 5 were lost.

The other slip is the return. When the loop ends, head still points at the old first node, which is now the last one. Returning it gave 1 -> null. The new head is prev.

The recursive version, and what it costs

Recursion reads nicely: reverse everything after head, then make the next node point back at head, and cut head's own pointer so it becomes the last node.

def reverse_recursive(head):
    if head is None or head.next is None:
        return head                     # an empty or one-node list is its own reverse
    new_head = reverse_recursive(head.next)   # reverse everything after head
    head.next.next = head               # the node after head now points back at it
    head.next = None                    # and head becomes the last node
    return new_head

It returned 5 -> 4 -> 3 -> 2 -> 1 -> null. Leave out head.next = None and the first two nodes point at each other: 5 -> 4 -> 3 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> ....

The price is the call stack: one frame per node, O(n) space, and every language caps how deep it can go. On our judge:

LanguageWorkedFailed
C++1,000,000 nodesnone at that size
Python (limit 1000)900 nodes1,000 nodes: RecursionError
Java5,000 nodes100,000 nodes: StackOverflowError
JavaScript5,000 nodes100,000 nodes: RangeError

So the loop is the answer to give, and the recursion is the follow-up you can explain and cost.

Reversing part of a list

Reverse Linked List II reverses only positions left to right. The loop doesn't change; what's new is the two ends. Walk to before, the node just before the part (a dummy covers left = 1). Call the part's first node first: it will end up last. Run the loop once per node of the part, right − left + 1 times. Then prev holds the part's new first node and curr the node after the part, and two writes put it back:

Positions 2 to 4 of 1 to 5 reversed in place: 4 → 3 → 2, with before on 1 and first on 2. Two numbered writes reconnect the part: before.next = prev points 1 at 4, and first.next = curr points 2 at 5. A crossed-out version shows the slip: without the second write, 2 points to null and 5 is lost.

Reverse positions 2 to 4 — The same loop runs three times between before and the node after the part; the last two steps are the writes that reconnect both ends.

Node* reverseBetween(Node* head, int left, int right) {
    Node dummy(0, head);
    Node* before = &dummy;
    for (int k = 1; k < left; k++)       // stop on the node before position left
        before = before->next;
    Node* first = before->next;          // the part's first node; it ends up last
    Node* prev = nullptr;
    Node* curr = first;
    for (int k = 0; k <= right - left; k++) {   // the same loop, once per node of the part
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    before->next = prev;                 // reconnect: the part's new first node...
    first->next = curr;                  // ...and its new last node to the rest
    return dummy.next;
}

def reverse_between(head, left, right):
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):           # stop on the node before position left
        before = before.next
    first = before.next                 # the part's first node; it ends up last
    prev, curr = None, first
    for _ in range(right - left + 1):   # the same loop, once per node of the part
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    before.next = prev                  # reconnect: the part's new first node...
    first.next = curr                   # ...and its new last node to the rest
    return dummy.next

static Node reverseBetween(Node head, int left, int right) {
    Node dummy = new Node(0, head);
    Node before = dummy;
    for (int k = 1; k < left; k++)       // stop on the node before position left
        before = before.next;
    Node first = before.next;            // the part's first node; it ends up last
    Node prev = null, curr = first;
    for (int k = 0; k <= right - left; k++) {   // the same loop, once per node of the part
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    before.next = prev;                  // reconnect: the part's new first node...
    first.next = curr;                   // ...and its new last node to the rest
    return dummy.next;
}

function reverseBetween(head, left, right) {
    const dummy = new Node(0, head);
    let before = dummy;
    for (let k = 1; k < left; k++)       // stop on the node before position left
        before = before.next;
    const first = before.next;           // the part's first node; it ends up last
    let prev = null, curr = first;
    for (let k = 0; k <= right - left; k++) {   // the same loop, once per node of the part
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    before.next = prev;                  // reconnect: the part's new first node...
    first.next = curr;                   // ...and its new last node to the rest
    return dummy.next;
}

Each printed 1 -> 4 -> 3 -> 2 -> 5 -> null for positions 2 to 4, 5 -> 4 -> 3 -> 2 -> 1 -> null for 1 to 5, 2 -> 1 -> 3 -> 4 -> 5 -> null for 1 to 2 (the dummy was before), and 5 -> null for a single node.

Now you run the loop

Below is the same list three times: reverse the whole of it, then positions 2 to 4, then positions 1 to 3 from a dummy. Pick each write yourself. Once a round of the loop is right, Repeat runs those four writes again. For the parts, the last two writes are yours to choose, and a wrong one shows the loop or the lost tail it makes.

Reverse a Part: run the reversal one write at a time, then put the part back

In groups of k

Reverse Nodes in k-Group reverses the list k nodes at a time and leaves a short last group alone. It's the part reversal on repeat: before each group, check that k nodes remain; reverse them; reconnect both ends; and the group's old first node, now its last, becomes before for the next group.

Reverse in groups of 2 — The dashed box is the dummy. Each step reverses one group and reconnects it; the last step finds too few nodes and stops.

Node* reverseKGroup(Node* head, int k) {
    Node dummy(0, head);
    Node* before = &dummy;
    while (true) {
        Node* probe = before;
        for (int i = 0; i < k; i++) {    // are there k nodes left?
            probe = probe->next;
            if (probe == nullptr) return dummy.next;   // fewer than k: they stay as they are
        }
        Node* first = before->next;
        Node* prev = nullptr;
        Node* curr = first;
        for (int i = 0; i < k; i++) {
            Node* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        before->next = prev;
        first->next = curr;
        before = first;                  // the group's new last node comes before the next group
    }
}

def reverse_k_group(head, k):
    dummy = Node(0, head)
    before = dummy
    while True:
        probe = before
        for _ in range(k):              # are there k nodes left?
            probe = probe.next
            if probe is None:
                return dummy.next       # fewer than k: they stay as they are
        first = before.next
        prev, curr = None, first
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
        before.next = prev
        first.next = curr
        before = first                  # the group's new last node comes before the next group

static Node reverseKGroup(Node head, int k) {
    Node dummy = new Node(0, head);
    Node before = dummy;
    while (true) {
        Node probe = before;
        for (int i = 0; i < k; i++) {    // are there k nodes left?
            probe = probe.next;
            if (probe == null) return dummy.next;   // fewer than k: they stay as they are
        }
        Node first = before.next;
        Node prev = null, curr = first;
        for (int i = 0; i < k; i++) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        before.next = prev;
        first.next = curr;
        before = first;                  // the group's new last node comes before the next group
    }
}

function reverseKGroup(head, k) {
    const dummy = new Node(0, head);
    let before = dummy;
    while (true) {
        let probe = before;
        for (let i = 0; i < k; i++) {    // are there k nodes left?
            probe = probe.next;
            if (probe === null) return dummy.next;   // fewer than k: they stay as they are
        }
        const first = before.next;
        let prev = null, curr = first;
        for (let i = 0; i < k; i++) {
            const next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        before.next = prev;
        first.next = curr;
        before = first;                  // the group's new last node comes before the next group
    }
}

Each printed 2 -> 1 -> 4 -> 3 -> 5 -> null for k = 2, 3 -> 2 -> 1 -> 4 -> 5 -> null for k = 3, 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> null for 1 to 6 in threes, and 1 -> 2 -> 3 -> null for k = 1. Counting ahead visits each node twice and the reversal once more, so it's still O(n) time and O(1) space.

A doubly linked list, and reversal as a step

A doubly linked list reverses by swapping each node's two pointers. After the swap, prev holds what was next, so that's how the walk moves on:

class DNode:
    def __init__(self, val):
        self.val, self.prev, self.next = val, None, None

def reverse_doubly(head):
    curr, last = head, None
    while curr is not None:
        curr.prev, curr.next = curr.next, curr.prev   # swap the two pointers
        last = curr
        curr = curr.prev                # prev now holds what was next
    return last                         # the old tail is the new head

On the doubly linked list 1, 2, 3, 4, reading the new head forward and the new tail backward gave [4, 3, 2, 1] [1, 2, 3, 4].

Reversal also shows up inside bigger problems. Palindrome Linked List in O(1) space reverses the second half from the middle, compares the halves, and reverses the second half back, so the caller's list is left as it was (Fast and Slow Pointers, next, explains finding the middle):

def is_palindrome(head):
    slow = fast = head
    while fast is not None and fast.next is not None:   # slow ends at the middle
        slow, fast = slow.next, fast.next.next
    second = reverse(slow)              # reverse the second half
    a, b, same = head, second, True
    while b is not None:
        if a.val != b.val:
            same = False
            break
        a, b = a.next, b.next
    reverse(second)                     # and put it back, so the caller's list is unchanged
    return same

It said True for 1 → 2 → 3 → 2 → 1 and True for 1 → 2 → 2 → 1, False for 1 → 2 → 3, and each list printed the same afterwards. Add 1 to a number represented as linked list reverses so the last digit comes first, adds with a carry, and reverses back:

def add_one(head):
    head = reverse(head)                # the last digit is now first
    curr, carry = head, 1
    while curr is not None and carry:
        total = curr.val + carry
        curr.val, carry = total % 10, total // 10
        if carry and curr.next is None:
            curr.next = Node(0)         # 999 + 1 needs one more digit
        curr = curr.next
    return reverse(head)

4 → 5 → 6 became 4 -> 5 -> 7 -> null and 9 → 9 → 9 became 1 -> 0 -> 0 -> 0 -> null.

Spotting it, and when it breaks

The clues. "Reverse" in the statement, of course, but also anything that needs the list from the back without extra space: compare the two halves, add numbers from the last digit, weave the end of the list into the front (Reorder List). A part or a group means the same loop plus reconnecting both ends.

The near-misses. A doubly linked list can be walked backwards from its tail without reversing anything. And if the caller still needs the original order, reversing in place changes it for everyone who holds a node: reverse it back afterwards, as the palindrome check does, or reverse a copy.

When it breaks. Recursion on long lists, as the table above shows; the loop has no such limit. Reversal never needs more than the three pointers, so if a solution reaches for a stack of nodes, it's the brute force in disguise.

Bugs that cost a submission

Flipping before saving. curr.next = prev first lost the rest: 1 -> null.

Returning head. The old head is the new tail: 1 -> null.

The recursive version without the cut. The first two nodes point at each other: 5 -> 4 -> 3 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> ....

Never reconnecting the part's last node. Reverse Linked List II without first.next = curr:

def reverse_between(head, left, right):
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):           # stop on the node before position left
        before = before.next
    first = before.next                 # the part's first node; it ends up last
    prev, curr = None, first
    for _ in range(right - left + 1):   # the same loop, once per node of the part
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    before.next = prev                  # reconnect: the part's new first node...
    return dummy.next

For positions 2 to 4 it gave 1 -> 4 -> 3 -> 2 -> null: 2 still points to null, and 5 is lost.

Reversing a short last group. Reverse Nodes in k-Group leaves fewer than k nodes alone. This version reverses whatever is left:

def reverse_k_group(head, k):
    dummy = Node(0, head)
    before = dummy
    while before.next is not None:      # reverses whatever is left, a short group too
        first = before.next
        prev, curr, count = None, first, 0
        while curr is not None and count < k:
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
            count += 1
        before.next = prev
        first.next = curr
        before = first
    return dummy.next

With k = 3 on 1 to 5 it returned 3 -> 2 -> 1 -> 5 -> 4 -> null; the answer is 3 -> 2 -> 1 -> 4 -> 5 -> null. Count k ahead before you touch a group.

Check yourself

Quiz

1 / 6

Multiple choice

Inside the loop, which write must come before curr.next = prev?

Practice problems

From easier to harder:

  1. Reverse Linked List: the loop, and the recursion as a follow-up.
  2. Reversing a Doubly Linked List: swap each node's two pointers.
  3. Reverse Linked List II: the loop between two fixed nodes, then reconnect both ends.
  4. Add 1 to a number represented as linked list: reverse, add with a carry, reverse back.
  5. Reverse Nodes in k-Group: count k ahead, reverse, reconnect, repeat.

Next, Fast and Slow Pointers: two pointers at different speeds, for the middle and for cycles.