Reverse a Linked List

time: O(n)
space: O(1)
tags: linked-lists · two-pointer

in the wild Reverse a transaction log to replay events in undo order; reverse a robot's trajectory chain for backtracking.

Problem

Given the head of a singly-linked list, reverse the list in-place and return the new head. Don't allocate a new list — just rewire the existing next pointers.

Examples

1 → 2 → 3 → 4 → ∅ becomes 4 → 3 → 2 → 1 → ∅
1 → ∅ returns 1 → ∅ (single node, nothing to do)
∅ returns ∅ (empty list)

Why this is the canonical pointer-manipulation problem

If you understand this problem, you understand linked lists. The whole exercise is in carefully reassigning three pointers per step without losing the rest of the list — drop one of them and the tail is unreachable forever.

The trick is to walk the list with a three-pointer "wave" — prev, cur, next — and at each node, redirect cur.next to point backward at prev, then slide the wave forward by one. After the wave passes the end, prev is the new head.

Hints

Hint 1 — what you can't lose

If you set cur.next = prev before saving cur.next somewhere, you've cut off the rest of the list and can't reach it. What temporary variable do you need before the rewire?

Hint 2 — the three-pointer dance

Maintain three pointers as you walk:

prev — the node we've just reversed onto (initially None)
cur — the node we're processing this step (initially head)
next — cur.next before we overwrite it

At each step: save next = cur.next, then cur.next = prev, then slide prev = cur; cur = next.

Hint 3 — recursive variant

Recursion works too: reverse the rest of the list, then attach head to the end:

fn reverse(head):
    if head is None or head.next is None: return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

O(n) time, but O(n) stack — the iterative version is preferred for long lists.

Solution

class Node:
    def __init__(self, val: int, nxt: "Node | None" = None):
        self.val, self.next = val, nxt

def reverse(head: Node | None) -> Node | None:
    prev, cur = None, head
    while cur:
        nxt = cur.next     # save next before we overwrite it
        cur.next = prev    # rewire backward
        prev, cur = cur, nxt
    return prev

# Helpers + tests — each prints the result
def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def collect(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

cases = [
    [1, 2, 3, 4],   # → [4, 3, 2, 1]
    [42],           # → [42]
    [],             # → []
]
for values in cases:
    got = collect(reverse(build(values)))
    expected = list(reversed(values))
    mark = "✓" if got == expected else "✗"
    print(f"{mark} reverse({values}) = {got}")

class Node {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const nxt = cur.next;   // save next before we overwrite it
    cur.next = prev;        // rewire backward
    prev = cur; cur = nxt;
  }
  return prev;
}

// Helpers + tests
const build = (vs) => vs.reduceRight((tail, v) => new Node(v, tail), null);
const collect = (head) => {
  const out = [];
  while (head) { out.push(head.val); head = head.next; }
  return out;
};

const cases = [
  [1, 2, 3, 4],   // → [4, 3, 2, 1]
  [42],           // → [42]
  [],             // → []
];
for (const values of cases) {
  const got = collect(reverse(build(values)));
  const expected = [...values].reverse();
  const ok = JSON.stringify(got) === JSON.stringify(expected);
  console.log(`${ok ? "✓" : "✗"} reverse(${JSON.stringify(values)}) = ${JSON.stringify(got)}`);
}

// Iterative — O(n) time, O(1) space.
pub struct Node {
    pub val: i32,
    pub next: Option<Box<Node>>,
}

pub fn reverse(head: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut prev: Option<Box<Node>> = None;
    let mut cur = head;
    while let Some(mut node) = cur {
        let next = node.next.take();   // save: what was cur.next
        node.next = prev;              // rewire: cur.next = prev
        prev = Some(node);             // slide: prev = cur
        cur = next;                    // slide: cur = next
    }
    prev
}

fn build(values: &[i32]) -> Option<Box<Node>> {
    let mut head = None;
    for &v in values.iter().rev() { head = Some(Box::new(Node { val: v, next: head })); }
    head
}
fn collect(mut head: Option<Box<Node>>) -> Vec<i32> {
    let mut out = vec![];
    while let Some(n) = head { out.push(n.val); head = n.next; }
    out
}

fn main() {
    let cases: &[&[i32]] = &[&[1, 2, 3, 4], &[42], &[]];
    for vs in cases {
        let got = collect(reverse(build(vs)));
        let expected: Vec<i32> = vs.iter().rev().copied().collect();
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} reverse({:?}) = {:?}", vs, got);
    }
}

#include <iostream>
#include <vector>
#include <memory>

struct Node {
    int val;
    std::unique_ptr<Node> next;
    Node(int v, std::unique_ptr<Node> nx = nullptr) : val(v), next(std::move(nx)) {}
};

std::unique_ptr<Node> reverse(std::unique_ptr<Node> head) {
    std::unique_ptr<Node> prev;
    auto cur = std::move(head);
    while (cur) {
        auto next = std::move(cur->next);   // save next
        cur->next = std::move(prev);        // rewire backward
        prev = std::move(cur);              // slide
        cur = std::move(next);
    }
    return prev;
}

std::unique_ptr<Node> build(const std::vector<int>& vs) {
    std::unique_ptr<Node> head;
    for (auto it = vs.rbegin(); it != vs.rend(); ++it)
        head = std::make_unique<Node>(*it, std::move(head));
    return head;
}
std::vector<int> collect(std::unique_ptr<Node> head) {
    std::vector<int> out;
    while (head) { out.push_back(head->val); head = std::move(head->next); }
    return out;
}

int main() {
    std::vector<std::vector<int>> cases = { {1,2,3,4}, {42}, {} };
    for (auto& vs : cases) {
        auto got = collect(reverse(build(vs)));
        std::vector<int> expected(vs.rbegin(), vs.rend());
        bool ok = got == expected;
        std::cout << (ok ? "✓" : "✗") << " reverse({";
        for (size_t i = 0; i < vs.size(); ++i) std::cout << vs[i] << (i + 1 < vs.size() ? "," : "");
        std::cout << "}) = {";
        for (size_t i = 0; i < got.size(); ++i) std::cout << got[i] << (i + 1 < got.size() ? "," : "");
        std::cout << "}\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int val; struct Node* next; } Node;

Node* reverse(Node* head) {
    Node* prev = NULL;
    Node* cur  = head;
    while (cur) {
        Node* next = cur->next;   // save next
        cur->next = prev;          // rewire backward
        prev = cur; cur = next;
    }
    return prev;
}

Node* build(const int* vs, int n) {
    Node* head = NULL;
    for (int i = n - 1; i >= 0; --i) {
        Node* node = malloc(sizeof(Node));
        node->val = vs[i]; node->next = head;
        head = node;
    }
    return head;
}
static void print_list(Node* head) {
    printf("[");
    for (Node* p = head; p; p = p->next) printf("%d%s", p->val, p->next ? "," : "");
    printf("]");
}
static void free_list(Node* head) {
    while (head) { Node* n = head->next; free(head); head = n; }
}

int main(void) {
    int a[] = {1, 2, 3, 4};
    Node* h1 = reverse(build(a, 4));
    printf("✓ reverse([1,2,3,4]) = "); print_list(h1); printf("\n");
    free_list(h1);

    int b[] = {42};
    Node* h2 = reverse(build(b, 1));
    printf("✓ reverse([42]) = "); print_list(h2); printf("\n");
    free_list(h2);

    Node* h3 = reverse(build(NULL, 0));
    printf("✓ reverse([]) = "); print_list(h3); printf("\n");
    free_list(h3);
    return 0;
}

idle

The three-pointer dance is the same in every language; what differs is who manages memory. Rust uses Option<Box<T>> + .take(). C++ uses std::unique_ptr + std::move. C uses raw Node* and you free() what you malloc(). Python and JS just let the garbage collector clean up.

Complexity

Time: O(n) — each node is visited and rewired exactly once.
Space: O(1) — three pointer variables, no auxiliary data structure. The recursive variant uses O(n) stack frames.

In the wild

Undo / redo history. Recording forward and then walking backward — reversing the chain is the cleanest way to replay in reverse.
Robotics trajectory backtracking. A robot's pose chain (linked) reversed gives you the return path.
Stack-based DFS recovery. When you've been pushing nodes onto a "visited in this order" linked list, reversing gives forward visit order.

Variations

Reverse in groups of k. Walk k nodes, reverse just those, attach. O(n) time, O(1) space, but the bookkeeping for the boundaries is fiddly.
Reverse a doubly-linked list. Even easier — just swap each node's prev and next pointers, then swap head and tail.
Reverse between positions m and n. Walk to m-1, reverse n - m + 1 nodes, stitch back together.