Skip to content

Volume ITechnology

4.9.1 — Reverse Linked List ​

LeetCode 206 · Easy · ★ Blind 75

The problem ​

You are given the head of a singly linked list. Reverse the list and return the new head.

A linked list is a chain of small objects called nodes. Each node holds a value, val, and a pointer, next, to the node after it. The last node's next is null (written None in Python), meaning "nothing after me". The head is the first node. Singly linked means each node only knows the node after it, not the one before. 4.7 builds linked lists from the ground up.

1 → 2 → 3 → 4 → 5 → null
becomes
5 → 4 → 3 → 2 → 1 → null

The list has between 0 and 5,000 nodes.

What the problem is really asking ​

We do not move any values. We turn every arrow around. Node 2 points at node 3 now. Afterwards, node 2 must point at node 1. The old head, node 1, must point at null, because it becomes the last node. And the old last node, 5, becomes the new head.

So the real question is: how do you turn each next pointer to face backwards, in one walk, without losing your way?

There is one danger. A node's next pointer is the only way to reach the rest of the list. The moment you overwrite curr.next to point backwards, you lose the way forward, unless you saved it first.

The brute force, and where it wastes memory ​

Copy the values into a list, then write them back in reverse order.

python
def reverseList(head):
    values = []
    node = head
    while node:
        values.append(node.val)
        node = node.next
    node = head
    while node:
        node.val = values.pop()        # take values from the end
        node = node.next
    return head

It is O(n) time, but it uses O(n) extra memory for the list. It also changes the values inside the nodes rather than the links, which an interviewer may not allow.

The waste in one sentence: it stores every value in a second list, when each arrow can be turned around on the spot using just three pointers.

The idea ​

Walk the list once with three pointers.

  • prev is the node you just came from. It starts as null.
  • curr is the node you are standing on. It starts at head.
  • nxt is a temporary note of the node after curr, saved before you change anything.

At each node, do four things in this order.

  1. Save the way forward: nxt = curr.next.
  2. Turn the arrow around: curr.next = prev.
  3. Step prev forward onto curr.
  4. Step curr forward onto nxt.

The figure shows one round of this, in three snapshots.

① before the roundnull123prevcurr② save nxt, then turn curr's arrownull123prevcurrnxt (saved)2 now points back at 1③ step both pointers forwardnull123prev = 2, curr = 3
One round of the loop. Green arrows are already reversed. The amber node is the saved way forward. The red arrow is the one being turned in this round.

Here is how to read it. In snapshot ①, node 1 already points back at null, and we are standing on node 2, which still points forward to 3. In snapshot ②, we first save node 3 as nxt, and only then turn node 2's arrow to point back at node 1. Without the saved nxt, nothing would lead to node 3 any more. In snapshot ③, prev moves to node 2 and curr moves to node 3, ready for the next round.

The solution ​

python
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None                  # (1)
        curr = head                  # (2)

        while curr:                  # (3)
            nxt = curr.next          # (4)
            curr.next = prev         # (5)
            prev = curr              # (6)
            curr = nxt               # (7)

        return prev                  # (8)
ts
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;  // (1)
  let curr = head;                   // (2)

  while (curr) {                     // (3)
    const nxt = curr.next;           // (4)
    curr.next = prev;                // (5)
    prev = curr;                     // (6)
    curr = nxt;                      // (7)
  }

  return prev;                       // (8)
}

Line by line ​

(1) prev = None. Nothing comes before the head. That is exactly right, because the old head will become the new last node, and the last node must point at null.

(2) curr = head. Start on the first node.

(3) Keep going while there is a node to stand on. When curr becomes None, we have walked off the end.

(4) Save the way forward. nxt remembers the node after curr. This must happen before line (5), because line (5) overwrites curr.next.

(5) Turn the arrow around. curr now points back at prev.

(6) Move prev forward onto the node we just fixed.

(7) Move curr forward onto the saved next node.

(8) Return prev, not curr. The loop stops when curr is None. At that moment prev is the last real node of the old list, which is the head of the reversed list. Returning curr would return None every time. That is the classic bug on this problem.

Trace ​

Take 1 → 2 → 3 → null.

After roundprevcurrArrows so far
startnull11 → 2 → 3 → null
1121 → null, and 2 → 3 still
2232 → 1 → null, and 3 → null still
33null3 → 2 → 1 → null

curr is null, so the loop stops. We return prev, which is node 3, the new head.

Complexity, derived ​

Time. Each node is visited exactly once, and each visit does four pointer assignments. So the time is O(n).

Space. Three pointer variables, whatever the length of the list. So the extra memory is O(1).

The recursive version ​

python
def reverseList(self, head):
    if not head or not head.next:             # (1)
        return head
    new_head = self.reverseList(head.next)    # (2)
    head.next.next = head                     # (3)
    head.next = None                          # (4)
    return new_head                           # (5)

(1) An empty list, or a list of one node, is already reversed.

(2) Reverse everything after this node. Trust the call to do it. It hands back the new head, which is the old last node.

(3) This is the line to slow down on. Say head is node 1, and node 2 comes after it. After line (2), nodes 2 onward are reversed, and node 2 is now the last node of that reversed part. head.next is still node 2, because we have not touched node 1's pointer yet. So head.next.next = head means "node 2's next is now node 1". That attaches node 1 to the end.

(4) Node 1 is now the last node, so it points at None.

(5) Pass the new head all the way back up.

It is short and neat, but it uses O(n) memory. Each call waits on the call stack until the calls below it finish, so a list of n nodes needs n waiting calls. Python stops at about 1,000 nested calls by default, so a 5,000-node list would crash. The loop version is the one to write.

Edge cases ​

  • Empty list. curr starts as None, the loop never runs, and we return prev, which is None. Correct.
  • One node. One round: the node points at None, and prev is that node. Correct.
  • Two nodes. Two rounds. A good size to trace by hand if you are unsure.

Variations you will meet ​

This is the most reused building block in the linked-list group. Get it into your fingers and half of 4.9 becomes assembly work.

  • Reverse Linked List II. Reverse only the nodes between positions left and right. Same loop, plus two extra pointers to the nodes just outside that stretch, so you can stitch it back in.
  • Reverse Nodes in k-Group. Reverse every block of k nodes. See 4.9.11.
  • Palindrome Linked List. Find the middle, reverse the second half, and compare the two halves.
  • Reorder List. Uses this exact loop as one of its three steps. See 4.9.3.

What the interviewer will push on ​

"Why save nxt first?" Because overwriting curr.next destroys the only way to reach the rest of the list.

"Why return prev and not curr?" When the loop ends, curr is None and prev is the old last node.

"Iterative or recursive?" Iterative. Same time, but O(1) memory instead of O(n), and no risk of a stack overflow on a long list.

"Walk me through head.next.next = head." Use node 1 and node 2 as above. Being able to explain this line clearly is what the question is testing.

One thing to volunteer: say that this loop is a building block, and name two problems that use it, such as Reorder List and Palindrome Linked List.

Next: 4.9.2 Merge Two Sorted Lists. The problem that introduces the dummy head, which removes almost every special case in this chapter.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet