What is the brute force approach and complexity for Reverse Linked List?

Push every node on a stack, then pop them back in reverse order with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Reverse Linked List?

Walk once, flip each arrow back, keep prev and cur with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Reverse Linked List?

Look for key signals in the prompt: "reverse the list" indicates Every arrow must flip. A linked list can't walk backwards, so we flip each arrow while walking forward.; "singly linked list" indicates Each node only knows its next node. Save the next node before you change an arrow.; "return the new head" indicates The old head becomes the last node. The new head is the last node we reach, which is the one prev holds..

Reverse Linked List

Easy·LeetCode #206Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLinked List — Reversal (full reversal, three pointers)

Complexity:O(N)→O(N)

Key Insight

Each node needs its arrow to point at the node before it. Walk the list once. Keep prev (the reversed part) and cur (the next node to flip). Save cur->next before each flip, so the rest of the list is not lost.

Core Validity Invariant

The list is reversed when every node's next points to the node before it in the original list, and the old head points to null.

Problem

You are given the head of a singly linked list. Reverse the list, so the last node becomes the first and every arrow points the other way. Return the new head.

Input

head, the first node of a singly linked list. The list can be empty.

Output

The head of the reversed list.

Example 1

Input: head = [1, 2, 3, 4, 5]

Output: [5, 4, 3, 2, 1]

Every arrow now points back towards the start.

Example 2

Input: head = [1, 2]

Output: [2, 1]

Only the one arrow between them flips. Node 2 now points to node 1, and node 1 points to null.

Example 3

Input: head = []

Output: []

An empty list has nothing to reverse.

Constraints

• The list has between 0 and 5000 nodes.
• -5000 ≤ Node.val ≤ 5000
• Follow-up: can you reverse the list both iteratively and recursively?

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I walk the list from the head, which arrow can I flip first? What do I lose when I flip it?
2.
After I flip the first arrow, can I still reach the second node? How?
3.
After the reversal, what should the old first node point to?
4.
How do I know when to stop, and which pointer holds the answer at that moment?
5.
Could I swap values from both ends, like an array? What stops me?

Brute force approach

Idea

A stack gives things back in the opposite order from how they went in. Push every node, then pop them off and link each popped node to the one after it. The answer is right, but the stack holds all n nodes at the same time.

Thinking process

1
We need the nodes in reverse order.
2
A stack returns the last thing pushed first. That is the order we want.
3
So push all the nodes, then pop them and link them up again.
4
On [1, 2, 3]: push 1, 2, 3. Pop 3, then 2, then 1, and link them in that order: 3 → 2 → 1 → null. That is the reversed list.

Code & Implementation

brute.cpp

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // Push every node onto a stack. Popping gives them back last-in, first-out,
        // which is exactly the reverse order.
        stack<ListNode*> st;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            st.push(cur);
        }
        // Pop them back and link each node to the one after it. We relink the same nodes.
        ListNode* newHead = nullptr;
        ListNode* tail = nullptr;
        while (!st.empty()) {
            ListNode* node = st.top();
            st.pop();
            if (tail == nullptr) newHead = node;
            else tail->next = node;
            tail = node;
        }
        // The old head is now the last node, so it must end the list.
        if (tail != nullptr) tail->next = nullptr;
        return newHead;
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        // Push every node onto a stack. Popping gives them back last-in, first-out,
        // which is exactly the reverse order.
        Deque<ListNode> st = new ArrayDeque<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            st.push(cur);
        }
        // Pop them back and link each node to the one after it. We relink the same nodes.
        ListNode newHead = null;
        ListNode tail = null;
        while (!st.isEmpty()) {
            ListNode node = st.pop();
            if (tail == null) newHead = node;
            else tail.next = node;
            tail = node;
        }
        // The old head is now the last node, so it must end the list.
        if (tail != null) tail.next = null;
        return newHead;
    }
}

from typing import Optional, List, Dict, Tuple

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Push every node onto a stack. Popping gives them back last-in, first-out,
        # which is exactly the reverse order.
        st: List[ListNode] = []
        cur = head
        while cur:
            st.append(cur)
            cur = cur.next
        # Pop them back and link each node to the one after it. We relink the same nodes.
        new_head = None
        tail = None
        while st:
            node = st.pop()
            if tail is None:
                new_head = node
            else:
                tail.next = node
            tail = node
        # The old head is now the last node, so it must end the list.
        if tail:
            tail.next = None
        return new_head

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function reverseList(head: ListNode | null): ListNode | null {
    // Push every node onto a stack. Popping gives them back last-in, first-out,
    // which is exactly the reverse order.
    const st: ListNode[] = [];
    for (let cur = head; cur !== null; cur = cur.next) {
        st.push(cur);
    }
    // Pop them back and link each node to the one after it. We relink the same nodes.
    let newHead: ListNode | null = null;
    let tail: ListNode | null = null;
    while (st.length > 0) {
        const node = st.pop()!;
        if (tail === null) newHead = node;
        else tail.next = node;
        tail = node;
    }
    // The old head is now the last node, so it must end the list.
    if (tail !== null) tail.next = null;
    return newHead;
}

Complexity

Time O(N)Space O(N)

The stack holds every node, so the extra memory grows with the list. The three-pointer version reverses in place with O(1) extra memory.

Optimized approach

Idea

Start from brute force

The stack copies every node so they come back in reverse. But each node only needs to remember the node that came before it. A single prev pointer does that, so no stack is needed.

Find the repeated work

The stack walks the list twice: once to push and once to pop. The three-pointer walk does everything in one pass, because each node is flipped as soon as we reach it.

Define the state — what variables do I need?

prev: The head of the part that is already reversed. It starts at null, because nothing is reversed yet.
cur: The first node we have not flipped. We walk forward through the original list with it.
nxt: The node after cur, saved before the flip, so the rest of the list is not lost.

Define validity

The list is reversed when every node's next points to the node before it in the original list, and the old head points to null.

Define the transitions — when does each pointer move, and why is it safe?

Every step

nxt = cur->next; cur->next = prev; prev = cur; cur = nxt;

Save nxt first. After the flip, cur->next points back, so the rest of the list can only be reached through nxt.

The loop ends (cur is null)

return prev;

prev is the last node we flipped, which was the old tail. The old tail is the new head.

What does the current window add to the answer?

Each step adds one node to the front of the reversed part. The reversed part always ends at null, so it is a valid list after every step.

Code & Implementation

optimal.cpp

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;   // the reversed part, built up behind us
        ListNode* cur = head;       // the first node we have not flipped yet
        while (cur != nullptr) {
            ListNode* nxt = cur->next;  // save the rest first, or we lose it when we flip cur
            cur->next = prev;           // flip this one arrow back to the reversed part
            prev = cur;
            cur = nxt;
        }
        // The loop ends with prev on the old tail. That node is the new head.
        return prev;
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;   // the reversed part, built up behind us
        ListNode cur = head;    // the first node we have not flipped yet
        while (cur != null) {
            ListNode nxt = cur.next;  // save the rest first, or we lose it when we flip cur
            cur.next = prev;          // flip this one arrow back to the reversed part
            prev = cur;
            cur = nxt;
        }
        // The loop ends with prev on the old tail. That node is the new head.
        return prev;
    }
}

from typing import Optional, List, Dict, Tuple

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None   # the reversed part, built up behind us
        cur = head    # the first node we have not flipped yet
        while cur:
            nxt = cur.next  # save the rest first, or we lose it when we flip cur
            cur.next = prev  # flip this one arrow back to the reversed part
            prev = cur
            cur = nxt
        # The loop ends with prev on the old tail. That node is the new head.
        return prev

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;   // the reversed part, built up behind us
    let cur: ListNode | null = head;    // the first node we have not flipped yet
    while (cur !== null) {
        const nxt: ListNode | null = cur.next;  // save the rest first, or we lose it when we flip cur
        cur.next = prev;                        // flip this one arrow back to the reversed part
        prev = cur;
        cur = nxt;
    }
    // The loop ends with prev on the old tail. That node is the new head.
    return prev;
}

Complexity

Time O(N)Space O(1)

The recursive version is also O(N) time, but each node uses a stack frame, so it needs O(N) memory. It is the same idea written as a function call, not a better approach. Use it as the follow-up answer, not as an upgrade.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Push every node on a stack, then pop them back in reverse order	O(N)	O(N)
Optimal	Walk once, flip each arrow back, keep prev and cur	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“reverse the list”Every arrow must flip. A linked list can't walk backwards, so we flip each arrow while walking forward.
“singly linked list”Each node only knows its next node. Save the next node before you change an arrow.
“return the new head”The old head becomes the last node. The new head is the last node we reach, which is the one prev holds.

walk forward once+flip one arrow per node+prev, cur, nxt→Linked List — Reversal (full reversal, three pointers)

This is the base of the whole reversal pattern: walk forward once and flip each arrow. Later questions reverse part of a list, or use this same move on a doubly linked list or in a number. The one rule to keep: before you change cur->next, save it. Each later question in this sub-pattern changes this basic move a little.

Don't make this mistake

Flipping the arrow before saving the rest of the list

✗ while (cur != nullptr) { cur->next = prev; prev = cur; cur = cur->next; // cur->next is now prev, so we jump backwards }

✓ while (cur != nullptr) { ListNode* nxt = cur->next; // save first cur->next = prev; prev = cur; cur = nxt; }

After cur->next = prev, the arrow no longer points to the rest of the list. The last line reads cur->next and gets the old prev, which is null on the first node. So cur becomes null, the loop stops after one node, and the rest of the list is lost.

Pattern confusion: swapping values from both ends, like an array

✗ ListNode* left = head; ListNode* right = lastNode(head); // a full walk to find the end while (left != right) { swap(left->val, right->val); left = left->next; // right would need to step backwards, which a singly linked list can't do }

✓ Flip the arrows with three pointers in one pass from the head.

Reversing an array by swapping from both ends works because you can jump straight to index n − 1 − i. A singly linked list can't step backwards, so right can't move inward. On [1, 2, 3, 4, 5], the first swap trades 1 and 5. The next pair is 2 and 4, and node 4 sits just before the tail, so it can only be found again with a walk from the head. Every pair repeats that walk, which makes the whole thing O(N²).

Returning the old head

✗ while (cur != nullptr) { ListNode* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } return head; // head is now the last node

✓ return prev; // the old tail is the new head

The old head was the first node, so its next is null after the reversal. Returning it gives back a list with one node. The new head is the last node we flipped, and prev holds it.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture