Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Reverse Linked List

EASYProblemSolveExternal Links

Description

Given the head of a singly linked list, reverse the list and return the new head (which was the original tail).

In a singly linked list, each node has a value and a pointer to the next node. The last node points to null. After reversing, every node's next pointer should point to its previous neighbor instead of its next neighbor. The original head becomes the new tail (pointing to null), and the original tail becomes the new head.

You should implement this both iteratively and recursively to fully understand the concept.

Examples

Example 1

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

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

Explanation: The original list is 1 → 2 → 3 → 4 → 5 → null. After reversing all the links, the list becomes 5 → 4 → 3 → 2 → 1 → null. Node 5 is now the head and node 1 is now the tail.

Example 2

Input: head = [1, 2]

Output: [2, 1]

Explanation: The list 1 → 2 → null becomes 2 → 1 → null. The only link (from node 1 to node 2) is reversed so that node 2 now points to node 1, and node 1 points to null.

Example 3

Input: head = []

Output: []

Explanation: The list is empty (head is null). There is nothing to reverse. Return null.

Constraints

  • The number of nodes in the list is in the range [0, 5000]
  • -5000 ≤ Node.val ≤ 5000

Editorial

Brute Force

Intuition

The most straightforward approach is to use a stack. A stack follows Last-In-First-Out (LIFO) order — the last element pushed is the first one popped. If we push all the nodes onto a stack, popping them gives us the nodes in reverse order.

Think of a stack of plates. You place plate 1 on the bottom, then 2 on top of it, then 3, then 4, and finally 5 on top. When you take plates off the stack, you get 5 first, then 4, then 3, then 2, then 1 — exactly the reverse order. We do the same with linked list nodes: push them all onto a stack, then pop them off one by one and link them together.

This approach is simple to understand but uses O(n) extra space for the stack, which is unnecessary since we can reverse the list in-place.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5]:

Step 1: Initialize an empty stack. Traverse the list and push all nodes except the last onto the stack.

Step 2: Push node 1 onto stack. Stack: [1]. Move to node 2.

Step 3: Push node 2 onto stack. Stack: [1, 2]. Move to node 3.

Step 4: Push node 3 onto stack. Stack: [1, 2, 3]. Move to node 4.

Step 5: Push node 4 onto stack. Stack: [1, 2, 3, 4]. Move to node 5.

Step 6: Node 5 has no next — it's the last node. Make it the new head. Set a pointer tail to node 5 to build the reversed list.

Step 7: Pop node 4 from stack. Set tail.next = node 4. Move tail to node 4. Stack: [1, 2, 3].

Step 8: Pop node 3 from stack. Set tail.next = node 3. Move tail to node 3. Stack: [1, 2].

Step 9: Pop node 2 from stack. Set tail.next = node 2. Move tail to node 2. Stack: [1].

Step 10: Pop node 1 from stack. Set tail.next = node 1. Move tail to node 1. Stack: [].

Step 11: Set tail.next = null (terminate the list). Reversed list: 5 → 4 → 3 → 2 → 1 → null.

Brute Force — Reverse Using Stack — Watch how nodes are pushed onto the stack in forward order and popped off in reverse order to build the reversed linked list.

Algorithm

  1. If head is null or has only one node, return head
  2. Create an empty stack
  3. Traverse the list, pushing all nodes except the last onto the stack
  4. The last node becomes the new head
  5. While the stack is not empty:
    a. Pop a node from the stack
    b. Set tail.next = popped node
    c. Move tail to the popped node
  6. Set tail.next = null (terminate the reversed list)
  7. Return the new head

Code

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        
        stack<ListNode*> stk;
        ListNode* temp = head;
        
        // Push all nodes except the last
        while (temp->next != nullptr) {
            stk.push(temp);
            temp = temp->next;
        }
        
        // Last node becomes new head
        ListNode* newHead = temp;
        
        // Pop and link nodes in reverse order
        while (!stk.empty()) {
            temp->next = stk.top();
            stk.pop();
            temp = temp->next;
        }
        
        temp->next = nullptr;
        return newHead;
    }
};
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        stack = []
        temp = head
        
        # Push all nodes except the last
        while temp.next:
            stack.append(temp)
            temp = temp.next
        
        # Last node becomes new head
        new_head = temp
        
        # Pop and link nodes in reverse order
        while stack:
            temp.next = stack.pop()
            temp = temp.next
        
        temp.next = None
        return new_head
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        
        // Push all nodes except the last
        while (temp.next != null) {
            stack.push(temp);
            temp = temp.next;
        }
        
        // Last node becomes new head
        ListNode newHead = temp;
        
        // Pop and link nodes in reverse order
        while (!stack.isEmpty()) {
            temp.next = stack.pop();
            temp = temp.next;
        }
        
        temp.next = null;
        return newHead;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list once to push nodes onto the stack — O(n). Then we pop all n nodes — O(n). Total: O(n).

Space Complexity: O(n)

The stack stores up to n-1 nodes. This is the main drawback of this approach — we use linear extra space that is entirely unnecessary, as the reversal can be done in-place.

Why This Approach Is Not Efficient

The stack-based approach uses O(n) extra space to store all the nodes. With up to 5000 nodes, this means allocating space for 5000 pointers in the stack — wasteful when we consider that a linked list can be reversed in-place using only three pointer variables.

The key insight is that we don't need to collect all nodes and then rebuild the list. Instead, we can reverse each link as we encounter it during a single traversal. At each node, we just need to know three things: the previous node (to point the current node backward), the current node (the one we're reversing), and the next node (to continue forward after we reverse the current link). These three pointers are all we need to reverse the list in O(1) space.

Optimal Approach - Iterative Three-Pointer Reversal

Intuition

We reverse the linked list in a single pass using three pointers: prev, curr, and next. At each step, we flip the current node's pointer from pointing forward to pointing backward.

Imagine a line of people each pointing to the person in front of them. You walk down the line and tell each person: "Stop pointing forward. Instead, point to the person behind you." Before you tell them, you first note who they're currently pointing to (so you know where to go next). Then you flip their direction. Then you step forward to the person they were originally pointing at.

The process:

  1. Save curr's next node (before we lose it)
  2. Point curr backward to prev
  3. Advance prev to curr
  4. Advance curr to the saved next

When curr reaches null, prev is pointing to the last node we processed — which is the new head of the reversed list.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5]:

Original: 1 → 2 → 3 → 4 → 5 → null

Step 1: Initialize prev = null, curr = node 1.

Step 2: Save next = curr.next = node 2. Reverse link: curr.next = prev = null. Now node 1 points to null (it will be the tail). Advance: prev = node 1, curr = node 2.

Step 3: Save next = curr.next = node 3. Reverse link: curr.next = prev = node 1. Now node 2 points backward to node 1. Advance: prev = node 2, curr = node 3.

Step 4: Save next = curr.next = node 4. Reverse link: curr.next = prev = node 2. Now node 3 points backward to node 2. Advance: prev = node 3, curr = node 4.

Step 5: Save next = curr.next = node 5. Reverse link: curr.next = prev = node 3. Now node 4 points backward to node 3. Advance: prev = node 4, curr = node 5.

Step 6: Save next = curr.next = null. Reverse link: curr.next = prev = node 4. Now node 5 points backward to node 4. Advance: prev = node 5, curr = null.

Step 7: curr is null — loop ends. prev = node 5, which is the new head. Reversed list: 5 → 4 → 3 → 2 → 1 → null.

Iterative Reversal — Flipping Links One by One — Watch as three pointers (prev, curr, next) walk through the list. At each step, curr's link is flipped from pointing forward to pointing backward.

Algorithm

  1. Initialize prev = null, curr = head
  2. While curr is not null:
    a. Save next = curr.next
    b. Reverse link: curr.next = prev
    c. Advance prev: prev = curr
    d. Advance curr: curr = next
  3. Return prev (the new head)

Code

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            ListNode* next = curr->next;  // Save next
            curr->next = prev;            // Reverse link
            prev = curr;                  // Advance prev
            curr = next;                  // Advance curr
        }
        
        return prev;  // prev is the new head
    }
};
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        
        while curr:
            next_node = curr.next  # Save next
            curr.next = prev       # Reverse link
            prev = curr            # Advance prev
            curr = next_node       # Advance curr
        
        return prev  # prev is the new head
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;  // Save next
            curr.next = prev;           // Reverse link
            prev = curr;                // Advance prev
            curr = next;                // Advance curr
        }
        
        return prev;  // prev is the new head
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list exactly once, visiting each of the n nodes one time. Each node requires O(1) work (save next, reverse link, advance pointers). Total: O(n).

Space Complexity: O(1)

We use only three pointer variables (prev, curr, next) regardless of the list size. No additional data structures are needed. This is a significant improvement over the stack-based approach which used O(n) space.