Reverse a Linked List (LeetCode 206)

Linked Lists are one of the most important data structures in Data Structures and Algorithms. A frequently asked interview question is reversing a singly linked list.

In this article, we'll understand the intuition, dry run, code implementation, and complexity analysis of the brute and optimal solution.

Brute Force

1. Intuition

The brute force approach relies on the Last-In, First-Out (LIFO) property of a Stack.

Since a linked list is unidirectional (nodes point from current to next), we cannot easily go backward. However, if we store all the nodes in a stack, the last node we pushed onto the stack will be the first one we pop. By popping them in reverse order and re-linking them, we effectively reverse the list.

Algorithm

• Check if the list is empty or has only one node; return it if so.
• Initialize an empty stack of type Node*.
• Traverse the linked list and push every node into the stack.
• Pop the top node from the stack and set it as the new head.
• Maintain a curr pointer to keep track of the node currently being processed in the new order.
• While the stack is not empty:
  • Pop the next node from the stack.
  • Point curr->next to this node.
  • Move curr to this node.
• Set the last node's next pointer to NULL to terminate the list.
• Return the new head.

#include <iostream>
#include <stack>

// This allows you to use stack, cout, cin without typing std::
using namespace std;

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        // Now you can just use 'stack' instead of 'std::stack'
        stack<ListNode*> s;
        ListNode* curr = head;

        while (curr != nullptr) {
            s.push(curr);
            curr = curr->next;
        }

        ListNode* newHead = s.top();
        s.pop();
        
        curr = newHead;
        while (!s.empty()) {
            curr->next = s.top();
            s.pop();
            curr = curr->next;
        }

        curr->next = nullptr;
        return newHead;
    }
};

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We traverse the list once to push and once to pop.
• Space Complexity: $O(N)$, because we store all $N$ nodes in the stack.

Alternate Approach

1. Intuition

Think of recursion as "diving" to the end of the list first. Once you reach the last node, you stop and start returning back. As you return, you flip the next pointer of each node to point to the node that preceded it in the recursion

Dry Run:

• Algorithm – Reverse a Linked List (Recursive Approach)

Idea:

• Keep moving recursively until you reach the last node.
• The last node becomes the new head.
• While returning (backtracking), reverse each link.

Steps

1. If the list is empty or has only one node, return that node.
2. Recursively reverse the remaining list starting from head->next.
3. Make the next node point back to the current node:
   • head->next->next = head
4. Break the old forward link:
   • head->next = NULL
5. Return the new head obtained from recursion.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        // Base Case
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // Recursively reverse the rest of the list
        ListNode* newHead = reverseList(head->next);

        // Reverse the link
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

Explanation

=========================================================
REVERSE LINKED LIST (RECURSIVE) - COMPLETE EXPLANATION
=========================================================

Input:
1 -> 2 -> 3 -> NULL


---------------------------------------------------------
STEP 1: RECURSIVE CALLS GO TILL THE LAST NODE
---------------------------------------------------------

reverse(1)
    reverse(2)
        reverse(3)

Node 3 is the last node.

Base Case:

if(head == NULL || head->next == NULL)
    return head;

So:

reverse(3) returns 3

newHead = 3


---------------------------------------------------------
STEP 2: BACKTRACKING STARTS AT NODE 2
---------------------------------------------------------

Current List:

2 -> 3 -> NULL


Code Executed:

head->next->next = head;


Substitution:

2->next->next = 2

Since:

2->next = 3

It becomes:

3->next = 2


Now the structure looks like:

2 -----> 3
^        |
|________|


A cycle is formed.

To break the old link:

head->next = NULL;

i.e.

2->next = NULL


Final Structure:

3 -> 2 -> NULL


---------------------------------------------------------
STEP 3: BACKTRACKING CONTINUES AT NODE 1
---------------------------------------------------------

Current List:

1 -> 2 -> NULL


Code Executed:

head->next->next = head;


Substitution:

1->next->next = 1

Since:

1->next = 2

It becomes:

2->next = 1


Now:

1 -----> 2
^        |
|________|


Again a cycle is formed.

Break the old link:

head->next = NULL;

i.e.

1->next = NULL


Final Structure:

3 -> 2 -> 1 -> NULL


---------------------------------------------------------
WHY THESE TWO LINES ARE IMPORTANT?
---------------------------------------------------------

head->next->next = head;
head->next = NULL;


Line 1:
---------

head->next->next = head;

Example:

2 -> 3

becomes

2 <- 3

It reverses the direction.


Line 2:
---------

head->next = NULL;

Removes the old forward connection.

Without this line:

2 <-> 3

Cycle will be formed.


---------------------------------------------------------
VISUALIZATION
---------------------------------------------------------

GOING DOWN (Recursive Calls)

1 -> 2 -> 3 -> 4 -> 5


COMING UP (Backtracking)

5 <- 4
5 <- 4 <- 3
5 <- 4 <- 3 <- 2
5 <- 4 <- 3 <- 2 <- 1


Final Answer:

5 -> 4 -> 3 -> 2 -> 1 -> NULL


---------------------------------------------------------
FULL CODE
---------------------------------------------------------

class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        if(head == NULL || head->next == NULL)
            return head;

        ListNode* newHead = reverseList(head->next);

        head->next->next = head;
        head->next = NULL;

        return newHead;
    }
};


---------------------------------------------------------
TIME & SPACE COMPLEXITY
---------------------------------------------------------

Time Complexity  : O(N)

Space Complexity : O(N)
                   (Recursion Stack)

=========================================================

Complexity Analysis:

---------------------------------------------------------
TIME COMPLEXITY
---------------------------------------------------------

Let N be the number of nodes.

For every node:

1. One recursive call is made.
2. During backtracking, only constant-time operations
   are performed:
   
   head->next->next = head;
   head->next = NULL;

Each node is visited exactly once.

Therefore:

T(N) = T(N-1) + O(1)

Solving:

T(N) = O(N)

Time Complexity = O(N)


---------------------------------------------------------
SPACE COMPLEXITY
---------------------------------------------------------

No extra data structures are used.

However, recursion uses the call stack.

Example:

reverse(1)
    reverse(2)
        reverse(3)
            reverse(4)
                reverse(5)

There are N function calls stored in memory.

Stack Space = O(N)

Therefore:

Space Complexity = O(N)


---------------------------------------------------------
WHY NOT O(1) SPACE?
---------------------------------------------------------

Many students think:

"No extra array, stack, or vector is used,
so space should be O(1)."

Wrong.

Recursive calls themselves occupy memory.

For N nodes:

Call Stack Size = N

Hence:

Auxiliary Space = O(N)


---------------------------------------------------------
FINAL ANSWER
---------------------------------------------------------

Time Complexity  : O(N)

Space Complexity : O(N)
                   (due to recursion call stack)

=========================================================

OPTIMAL APPROACH

Intuition

Suppose we have:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

We want:

5 -> 4 -> 3 -> 2 -> 1 -> NULL

The problem is that when we reverse a link, we might lose access to the remaining nodes.

For example:

1 -> 2 -> 3 -> NULL

If we directly do:

1->next = NULL;

then we lose the connection to node 2 and node 3.

So before changing any link, we first save the next node.

That's why we use 3 pointers in this approach:

• prev → previous node
• curr → current node
• next → next node (saved temporarily)

For every node:

1. Save next node.
2. Reverse current link.
3. Move all pointers one step ahead.

Repeat until the list ends.

Algorithm

ALGORITHM: Reverse Linked List (Iterative)

1. INITIALIZE:
   prev = NULL
   curr = head

2. WHILE curr IS NOT NULL:
   a. Store next node:
      next = curr->next
   
   b. Reverse link:
      curr->next = prev
   
   c. Move pointers forward:
      prev = curr
      curr = next

3. RETURN prev (This is the new head)

DRY RUN

To perform a dry run of the iterative algorithm, let's take a sample list: 1 -> 2 -> 3 -> NULL.

Here is the step-by-step trace of how the pointers behave.

Initial State

• prev = NULL
• curr = 1

Step-by-Step Execution

Iteration 1 (Processing node 1)

1. Store next: next = 2
2. Reverse link: 1->next = NULL (1 now points to prev)
3. Move pointers: prev = 1, curr = 2

• List status: NULL <- 1 2 -> 3 -> NULL

Iteration 2 (Processing node 2)

1. Store next: next = 3
2. Reverse link: 2->next = 1 (2 now points to prev)
3. Move pointers: prev = 2, curr = 3

• List status: NULL <- 1 <- 2 3 -> NULL

Iteration 3 (Processing node 3)

1. Store next: next = NULL
2. Reverse link: 3->next = 2 (3 now points to prev)
3. Move pointers: prev = 3, curr = NULL

• List status: NULL <- 1 <- 2 <- 3

Finalization

• Loop Condition: curr is now NULL, so the loop terminates.
• Return: We return prev, which is currently pointing to Node 3.
• Result: 3 -> 2 -> 1 -> NULL

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode* prev = nullptr;
        ListNode* curr = head;
        ListNode* next = nullptr;

        while (curr != nullptr) {
            
            next = curr->next;     // Store next node

            curr->next = prev;     // Reverse link

            prev = curr;           // Move prev forward
            curr = next;           // Move curr forward
        }

        return prev;
    }
};

Complexity Analysis:

---------------------------------------------------------
TIME COMPLEXITY
---------------------------------------------------------

Let N be the number of nodes in the linked list.

The while loop runs once for each node.

For every iteration, only constant-time operations
are performed:

1. next = curr->next
2. curr->next = prev
3. prev = curr
4. curr = next

Each operation takes O(1) time.

Since there are N nodes:

Total Time = N × O(1)

Time Complexity = O(N)


---------------------------------------------------------
SPACE COMPLEXITY
---------------------------------------------------------

Only three extra pointers are used:

prev
curr
next

Regardless of the size of the linked list,
the number of extra variables remains constant.

No recursion stack.
No extra array/vector/stack.

Space Complexity = O(1)

problem:

Reverse Linked List - LeetCode

Video reference:

L9. Reverse a LinkedList | Iterative and Recursive