Reverse Linked List

LeetCode 206: Reverse Linked List Solution & Explanation

Problem Overview

TL;DR: The optimal solution iterates through the linked list once, changing each node's next pointer to point to the previous node instead of the next one, requiring only constant extra space.

The Reverse Linked List problem asks us to take the head of a singly linked list and invert the sequence of nodes. If the original list is $1 \rightarrow 2 \rightarrow 3$, the result should be $3 \rightarrow 2 \rightarrow 1$. This is a fundamental LeetCode 206 challenge that tests your ability to manipulate pointers without losing track of the data structure's connectivity. It is a highly popular interview question because it serves as a building block for more complex linked list problems.

Brute Force Approach for Reverse Linked List

A common naive approach to solving Reverse Linked List is to treat the data structure like an array rather than a list of pointers.

In this approach, one might iterate through the linked list, collect all the values into an auxiliary data structure (like an array or a vector), reverse that array, and then construct a completely new linked list using the reversed values. Alternatively, one might use a Stack data structure to push all nodes onto the stack and then pop them off to form the reversed order.

Pseudo-code for Naive Approach

function reverseList(head):
    if head is null return null
    
    stack = new Stack()
    current = head
    
    // Push all nodes onto stack
    while current is not null:
        stack.push(current)
        current = current.next
        
    // Pop to create new order
    newHead = stack.pop()
    current = newHead
    
    while stack is not empty:
        node = stack.pop()
        current.next = node
        current = node
        
    current.next = null // Terminate list
    return newHead

Analysis

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We traverse the list twice (once to push, once to pop).
• Space Complexity: $O(N)$. We store all nodes (or values) in an external data structure.

Why it Fails

While this solution produces the correct output, it is suboptimal for interviews. The problem constraints allow for $N$ up to 5000, which fits in memory, but the core challenge of linked lists is usually in-place manipulation. Using $O(N)$ space defeats the purpose of using a linked list, which is designed for efficient pointer-based operations. In a system with limited memory or very large lists, allocating a parallel data structure is inefficient.

Algorithm Strategy: Linked List Manipulation Patterns

The strategy utilizes the In-place Reversal pattern to reverse the list in a single pass with $O(1)$ space.

1. Initialization: We start with two pointers. prev is initialized to null because the new tail of the list (originally the head) must point to nothing. curr is initialized to head.
2. Pointer Rotation: Inside a loop, we perform a specific four-step pointer rotation.
   • Save the next node.
   • Reverse the current pointer.
   • Advance prev.
   • Advance curr.
3. Boundary Enforcement: The loop continues until curr becomes null. This indicates we have processed the last node (the original tail).
4. Result: When the loop terminates, curr is null, and prev sits at the last non-null node processed, which is the new head of the reversed list.

Execution Flow

Let's trace the execution for head = [1, 2, 3].

1. Initial State:

   • prev = null
   • curr = Node(1)

2. Iteration 1 (Processing Node 1):

   • next_temp = curr.next (Node 2). Save reference to rest of list.
   • curr.next = prev (null). Reverse the link. Node 1 now points to null.
   • prev = curr (Node 1). Move prev forward.
   • curr = next_temp (Node 2). Move curr forward.

3. Iteration 2 (Processing Node 2):

   • next_temp = curr.next (Node 3).
   • curr.next = prev (Node 1). Reverse the link. Node 2 now points to Node 1.
   • prev = curr (Node 2).
   • curr = next_temp (Node 3).

4. Iteration 3 (Processing Node 3):

   • next_temp = curr.next (null).
   • curr.next = prev (Node 2). Reverse the link. Node 3 now points to Node 2.
   • prev = curr (Node 3).
   • curr = next_temp (null).

5. Termination:

   • curr is null. The loop ends.
   • Return prev (Node 3).

The resulting structure is $3 \rightarrow 2 \rightarrow 1 \rightarrow \text{null}$.

Proof of Correctness

The correctness of this algorithm relies on the loop invariant: At the start of every iteration, prev points to the head of the reversed portion of the list processed so far, and curr points to the head of the remaining original list.

• Initialization: prev is null (empty reversed list), curr is head (full original list). The invariant holds.
• Maintenance: In each step, we take the head of the remaining list (curr), point it to the reversed list (prev), and update prev to be this new head. effectively moving one node from the "remaining" set to the "reversed" set.
• Termination: When curr becomes null, the "remaining" list is empty. Therefore, by the invariant, prev must point to the head of the fully reversed list.

Pattern Reuse Notes

The Linked List - In-place Reversal pattern is a critical building block for several other problems. Mastering the logic of prev, curr, and next_temp enables you to solve:

• LeetCode 83: Remove Duplicates from Sorted List (Uses similar pointer traversal logic)
• LeetCode 92: Reverse Linked List II (Requires reversing only a specific sub-segment of the list)
• LeetCode 25: Reverse Nodes in k-Group (Applies the reversal logic repeatedly in groups of $k$)
• LeetCode 234: Palindrome Linked List (Requires reversing the second half of the list to compare with the first half)

Understanding LeetCode 206 is a prerequisite for these more advanced interview questions.

Reference Implementation

C++ Solution for LeetCode 206

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* reverseList(ListNode* head) {
14        ListNode* prev = nullptr;
15        ListNode* curr = head;
16        
17        while (curr != nullptr) {
18            // Save the next node so we don't lose the rest of the list
19            ListNode* nextTemp = curr->next;
20            
21            // Reverse the pointer direction
22            curr->next = prev;
23            
24            // Advance pointers
25            prev = curr;
26            curr = nextTemp;
27        }
28        
29        // prev is now the new head of the reversed list
30        return prev;
31    }
32};

Java Solution for LeetCode 206

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public ListNode reverseList(ListNode head) {
13        ListNode prev = null;
14        ListNode curr = head;
15        
16        while (curr != null) {
17            // Save the next node so we don't lose the rest of the list
18            ListNode nextTemp = curr.next;
19            
20            // Reverse the pointer direction
21            curr.next = prev;
22            
23            // Advance pointers
24            prev = curr;
25            curr = nextTemp;
26        }
27        
28        // prev is now the new head of the reversed list
29        return prev;
30    }
31}

Python Solution for LeetCode 206

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
8        prev = None
9        curr = head
10        
11        while curr:
12            # Save the next node
13            next_temp = curr.next
14            
15            # Reverse the pointer direction
16            curr.next = prev
17            
18            # Advance pointers
19            prev = curr
20            curr = next_temp
21            
22        # prev is now the new head of the reversed list
23        return prev