Reverse Linked List Algorithm Solutions

The reverse linked list problem is a fundamental coding interview question that tests understanding of pointer manipulation and recursion. This solution covers both iterative and recursive approaches with detailed complexity analysis and practical implementation considerations.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the linked list? (e.g., up to 5000 nodes, or unbounded?)
2. Are duplicate values allowed in the list?
3. Should I return a new list or mutate the original list?
4. Can I modify the input structure, or must I preserve it?
5. What is the target time complexity for follow-ups? (e.g., O(n) is required, or can we accept O(n²) for a simpler approach?)

Restate the pattern or problem type in your own words: The reverse linked list pattern involves taking a singly-linked list and reversing the direction of all its pointers so that the last node becomes the first, and the first becomes the last. This is a fundamental operation in linked list manipulation that tests understanding of pointer manipulation and iterative vs recursive approaches.

Clarify the signal words and constraint shape that point to it:

• Signal words: "reverse", "linked list", "nodes", "pointers"
• Constraint shape: singly-linked list (no backward traversal), typically requires in-place modification for efficiency
• The problem often asks to "reverse the list" or "return the reversed list"

Note any assumptions you are making:

• The input is a valid singly-linked list (no cycles)
• We're working with a standard linked list structure where each node has val and next fields
• The problem likely expects an in-place reversal for optimal space complexity

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily designed for static input scenarios where the entire list is available upfront. It's not typically used in streaming or online contexts since reversing requires knowledge of the full structure to properly rewire all pointers. However, it can be part of a larger pipeline where the list is processed once and then consumed in reverse order.

The pattern represents a canonical problem for understanding pointer manipulation in linked lists, with applications in list reversal algorithms, palindrome detection, and various list-based data structure operations.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Reverse" or "invert" operations on linked lists
• "K group reverse" or "reverse in groups of k"
• "Palindrome" problems where list reversal helps verify symmetry
• "Detect cycle" or "find intersection" where reversing can help with traversal logic

Why this pattern fits better than the most common alternatives: The reverse linked list pattern is specifically designed for manipulating node pointers in singly-linked structures. Unlike array-based reversal which can be done in-place with O(1) extra space, linked list reversal requires careful pointer manipulation. It's more efficient than converting to array and back (O(n) time + O(n) space), or using recursion with stack simulation (O(n) space). The iterative approach is optimal for the linked list structure.

Conditions where a variation or related pattern applies instead:

• For doubly-linked lists, reversal is simpler since we can traverse backward from tail
• For circular linked lists, the reversal logic changes to handle the cycle properly
• For problems requiring "reverse every k nodes" or "reverse in groups", we need to track group boundaries and handle partial groups
• When we're actually looking for "reverse order traversal" rather than structural reversal, tree traversal patterns might be more appropriate

The core insight that makes this pattern work: The key insight is that we need to carefully manage three consecutive nodes at any time: current node, previous node, and next node. By maintaining references to these three nodes, we can effectively reverse the direction of pointers without losing track of any part of the list. This allows us to process each node once and achieve O(n) time complexity with O(1) space usage.

3. Approach Evolution

Interview communication script:

"My first instinct is to reverse a linked list by changing the direction of pointers, which would be O(n) time and O(1) space. But I need to think carefully about how to do this without losing references to nodes. Let me trace through what happens when I try to reverse a simple list like 1->2->3->null.

If I start with head = 1, and try to make 1 point to null, I lose access to node 2. So I need to keep track of the previous node and the next node before modifying any pointers.

Let me think about this more systematically. I notice that if I maintain the invariant that I always have references to current node, previous node, and next node, I can traverse the list once and reverse all pointers in one pass. This is better than a brute force approach that would require multiple passes or recursion.

The key insight is that I need to process nodes in order while maintaining references to three consecutive nodes at each step. This way, I can safely update pointers without losing the ability to continue traversal."

Brute-force approach and why it is not ideal:

The brute force approach would be to:

1. Traverse the list once to collect all values in an array
2. Traverse again to put values back in reverse order
3. Or create a completely new list with reversed order

This is O(n) time but O(n) space, and requires two passes through the list. It's inefficient because we're using extra space unnecessarily when we can reverse in-place.

Improved approach and the key optimization:

The improved approach uses three pointers (prev, current, next) to reverse the list in a single pass. The key optimization is maintaining three references at each step:

• prev keeps track of the previous node (which will become the next node after reversal)
• current is the node we're currently processing
• next preserves reference to the next node before we lose it

This allows us to process each node exactly once while maintaining all necessary references.

Final approach with step-by-step reasoning:

1. Initialize three pointers: prev = null, current = head, next = null
2. While current is not null:
   • Store the next node in next pointer
   • Reverse the current node's pointer to point to prev
   • Move prev forward to current node
   • Move current forward to the stored next node
3. Return prev as the new head (since it becomes the last node in original list)

The key invariant that must hold is: at each step, we have references to exactly three consecutive nodes in the original list, allowing safe pointer reversal without data loss.

Important invariants that must hold:

1. next always stores reference to the node that comes after current before we modify current's pointer
2. prev always points to the node that should come after current in the reversed list
3. We never lose reference to any node that we might need to process later
4. The loop condition ensures we process each node exactly once

4. Data Structure Choice

The primary data structure used is the Singly Linked List Node with the following structure:

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

Why this data structure is needed:

• The problem explicitly requires working with a singly linked list structure
• Each node needs to store both the value and a reference to the next node
• The next pointer is essential for traversing and re-linking the list during reversal

Time and space impact:

• Time: O(1) for node creation and access operations
• Space: O(1) per node, O(n) total space where n is the number of nodes in the list

Helper structures:

• No additional helper data structures are needed for the core reversal algorithm
• The solution uses only three pointers (prev, current, and next) to track the state during reversal
• These are simple local variables rather than complex data structures

The simplicity of the linked list node structure makes this an ideal use case for direct pointer manipulation without requiring additional memory structures or complex data types. The solution's efficiency stems from working directly with the existing node structure rather than creating new containers or collections.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: 1 -> 2 -> 3 -> 4 -> null

Step 1: Initialize pointers

• prev = null
• current = 1 -> 2 -> 3 -> 4 -> null

Step 2: Process first node (value 1)

• Save next node: next = 2 -> 3 -> 4 -> null
• Reverse pointer: current.next = null (1 now points to null)
• Move pointers: prev = 1 -> null, current = 2 -> 3 -> 4 -> null

Step 3: Process second node (value 2)

• Save next node: next = 3 -> 4 -> null
• Reverse pointer: current.next = 1 -> null (2 now points to 1)
• Move pointers: prev = 2 -> 1 -> null, current = 3 -> 4 -> null

Step 4: Process third node (value 3)

• Save next node: next = 4 -> null
• Reverse pointer: current.next = 2 -> 1 -> null (3 now points to 2)
• Move pointers: prev = 3 -> 2 -> 1 -> null, current = 4 -> null

Step 5: Process fourth node (value 4)

• Save next node: next = null
• Reverse pointer: current.next = 3 -> 2 -> 1 -> null (4 now points to 3)
• Move pointers: prev = 4 -> 3 -> 2 -> 1 -> null, current = null

Step 6: Termination

• current is now null, so we exit the loop
• Return prev which points to the new head: 4 -> 3 -> 2 -> 1 -> null

The key insight is that we're essentially reversing the direction of links one at a time while maintaining references to the nodes we haven't processed yet, ensuring no node is lost during the reversal process.

graph LR
    A[1] --> B[2]
    B --> C[3]
    C --> D[4]
    D --> E[null]
    
    style A fill:#f9f,stroke:#333
    style B fill:#f9f,stroke:#333
    style C fill:#f9f,stroke:#333
    style D fill:#f9f,stroke:#333
    style E fill:#f9f,stroke:#333
    
    subgraph "Before"
        A
        B
        C
        D
        E
    end
    
    subgraph "After"
        F[4]
        G[3]
        H[2]
        I[1]
        J[null]
    end
    
    F --> G
    G --> H
    H --> I
    I --> J

6. Java Solution

/**
 * Definition for singly-linked list.
 * public 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) {
        // Base case: empty list or single node
        if (head == null || head.next == null) {
            return head;
        }
        
        // Three-pointer approach to reverse the linked list
        ListNode prev = null;      // Previous node (will become next node in reversed list)
        ListNode current = head;   // Current node being processed
        ListNode next = null;      // Temporary storage for next node
        
        // Iterate through the list until we reach the end
        while (current != null) {
            // Store the next node before we lose reference to it
            next = current.next;
            
            // Reverse the link: point current node to previous node
            current.next = prev;
            
            // Move pointers forward
            prev = current;      // Previous becomes current node
            current = next;      // Current becomes next node (from original list)
        }
        
        // When loop ends, prev points to the new head of reversed list
        return prev;
    }
}

The solution uses the classic three-pointer technique to reverse a singly linked list in-place. We maintain references to the previous node, current node, and next node to properly rewire the links while traversing the list once. The algorithm handles edge cases like empty lists and single-node lists naturally through the base case check.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm processes each node in the linked list exactly once. We traverse the list from head to tail, performing constant-time operations (node pointer updates) at each step. Since we visit each of the n nodes exactly once, the time complexity is linear.

Space Complexity: O(1)

The space complexity is constant because we only use a fixed number of pointer variables (current, next, previous) regardless of the input size. We don't use any recursive call stack or auxiliary data structures that scale with input size. The algorithm modifies the list in-place, requiring only a constant amount of extra memory for the three pointers needed during the reversal process.

Why these bounds are correct:

The linear time bound is tight because we must examine each node at least once to reverse the links properly. There's no way to determine the new order of nodes without visiting them all. The constant space bound is optimal for an in-place reversal operation - we cannot avoid using a constant number of pointers to track our position and maintain the reversal process.

Optimality:

This solution is optimal for the in-place linked list reversal problem. Any correct solution must process all nodes at least once to establish the new ordering, making O(n) time unavoidable. The O(1) space complexity is also optimal for in-place operations since we're not allowed to use additional data structures that grow with input size. The solution achieves both optimal time and space complexity for this canonical problem.

The algorithm's efficiency stems from its single-pass nature and minimal memory footprint, making it ideal for systems with constrained resources or when maintaining the original list structure is not required.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: The solution must handle null head gracefully. The algorithm should return null without any operations.
• Single node: A list with only one node should return that same node as the new head. The next pointer becomes null, which is correct.
• Two nodes: Edge case where the reversal involves exactly two nodes, requiring careful pointer updates.

Duplicate Values and Repeated States

• Duplicate values: The algorithm works identically regardless of whether node values are unique. No special handling is required for duplicate values.
• Self-referencing cycles: If the input list contains cycles (e.g., a node points to itself or creates a loop), this is not a valid singly linked list and would cause infinite loops during reversal. This is an invalid input that should not be handled in the solution.

Boundary Conditions

• Large lists: For very large lists (e.g., 10^6 nodes), ensure that the iterative approach is used to avoid stack overflow from recursive solutions.
• Null pointers: Ensure that next pointers are checked before dereferencing to prevent NullPointerException.

Common Implementation Mistakes

• Incorrect pointer updates: A frequent mistake is updating the current pointer before saving the next node, which causes loss of reference to the remaining list.
• Not handling null head: Failing to check for a null input head leads to runtime errors.
• Incorrect loop termination: Using the wrong condition in a while loop (e.g., while(current != null) instead of while(current != null && current.next != null)) can cause incorrect reversal or infinite loops.
• Memory leaks in languages with manual GC: Though not applicable in Java, in systems where memory management is manual, failing to properly release old node references can lead to memory leaks.

// Example of incorrect pointer handling:
// current.next = prev; // This breaks the link to remaining list
// current = current.next; // Now we've lost access to the rest of the list

9. Alternative Approaches

There are several alternative approaches to reversing a linked list, each with different trade-offs:

Recursive Approach:

public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

This approach uses O(n) space due to the call stack and is less efficient for very large lists. However, it's more intuitive and mirrors the mathematical definition of reversal.

Stack-Based Iterative Approach:

public ListNode reverseListWithStack(ListNode head) {
    if (head == null) return null;
    Stack<ListNode> stack = new Stack<>();
    ListNode current = head;
    
    while (current != null) {
        stack.push(current);
        current = current.next;
    }
    
    ListNode newHead = stack.pop();
    current = newHead;
    
    while (!stack.isEmpty()) {
        current.next = stack.pop();
        current = current.next;
    }
    current.next = null;
    
    return newHead;
}

This approach uses O(n) extra space for the stack and is less efficient than the two-pointer approach. It's useful for demonstrating understanding of stack-based solutions but adds unnecessary complexity.

Three-Pointer Technique with Extra Variables:

public ListNode reverseListThreePointers(ListNode head) {
    if (head == null || head.next == null) return head;
    
    ListNode prev = null;
    ListNode current = head;
    ListNode next = null;
    
    while (current != null) {
        next = current.next;  // Store next node
        current.next = prev;  // Reverse the link
        prev = current;       // Move prev forward
        current = next;       // Move current forward
    }
    
    return prev;
}

This is essentially the same as our main solution but with more explicit variable names. The key difference is that it's more readable and explicitly manages the three pointers.

The iterative two-pointer approach used in our main solution is preferred because it's:

1. Space-efficient (O(1) space)
2. Time-efficient (O(n) time)
3. Easy to understand and maintain
4. No risk of stack overflow for large inputs

The recursive approach, while elegant, has higher space complexity and can cause stack overflow issues for large lists. The stack-based approach adds unnecessary complexity without benefits over the direct iterative solution.

10. Test Cases

public class ReverseLinkedListTests {
    
    // Test case 1: Basic functionality with multiple nodes
    @Test
    public void testBasicReverse() {
        // Input: 1 -> 2 -> 3 -> 4 -> 5
        // Expected: 5 -> 4 -> 3 -> 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        ListNode result = reverseList(head);
        assertLinkedListEquals(new int[]{5,4,3,2,1}, result);
    }
    
    // Test case 2: Single node
    @Test
    public void testSingleNode() {
        // Input: 1
        // Expected: 1
        ListNode head = new ListNode(1);
        ListNode result = reverseList(head);
        assertLinkedListEquals(new int[]{1}, result);
    }
    
    // Test case 3: Empty list
    @Test
    public void testEmptyList() {
        // Input: null
        // Expected: null
        ListNode result = reverseList(null);
        assertNull(result);
    }
    
    // Test case 4: Two nodes
    @Test
    public void testTwoNodes() {
        // Input: 1 -> 2
        // Expected: 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        ListNode result = reverseList(head);
        assertLinkedListEquals(new int[]{2,1}, result);
    }
    
    // Test case 5: Duplicate values
    @Test
    public void testDuplicateValues() {
        // Input: 1 -> 2 -> 2 -> 3
        // Expected: 3 -> 2 -> 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        ListNode result = reverseList(head);
        assertLinkedListEquals(new int[]{3,2,2,1}, result);
    }
    
    // Test case 6: Large list (boundary condition)
    @Test
    public void testLargeList() {
        // Input: 1 -> 2 -> ... -> 1000
        // Expected: 1000 -> 999 -> ... -> 1
        ListNode head = createLinkedList(1, 1000);
        ListNode result = reverseList(head);
        assertLinkedListEquals(createExpectedArray(1000, 1), result);
    }
    
    // Helper methods for testing
    private ListNode createLinkedList(int start, int end) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int i = start; i <= end; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }
        return dummy.next;
    }
    
    private int[] createExpectedArray(int start, int end) {
        int[] result = new int[start - end + 1];
        int index = 0;
        for (int i = start; i >= end; i--) {
            result[index++] = i;
        }
        return result;
    }
    
    private void assertLinkedListEquals(int[] expected, ListNode actual) {
        int index = 0;
        while (actual != null && index < expected.length) {
            assertEquals(expected[index++], actual.val);
            actual = actual.next;
        }
        assertNull(actual);
        assertEquals(expected.length, index);
    }
}

11. Final Summary

The core idea is to reverse a singly linked list by iteratively reorienting node pointers from right-to-left, maintaining the chain integrity throughout the transformation. This solution works efficiently by using three pointers to track the previous, current, and next nodes during traversal, ensuring no links are lost. The approach is optimal with O(n) time and O(1) space complexity, making it ideal for scenarios where memory constraints are strict and the input can be modified in-place.