Reverse Linked List Algorithm Solutions

The reverse linked list problem is a fundamental coding challenge that tests understanding of pointer manipulation and algorithmic thinking. This solution covers both iterative and recursive approaches with detailed complexity analysis and practical implementation considerations for technical interviews at top tech companies.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we mutate the input linked list, or do we need to create a new one?
2. What is the expected time complexity constraint? Are we aiming for O(n) or better?
3. Are there any constraints on the size of the linked list (e.g., max nodes)?
4. Should we handle edge cases like empty list or single-node list?
5. Do we need to return the new head of the reversed list, or can we just modify the structure?

Restatement in my own words: The problem asks us to reverse the direction of a singly linked list so that the last node becomes the first, and the first becomes the last. This is a classic linked list manipulation problem that tests understanding of pointer management and iterative vs recursive approaches.

Clarification of inputs, outputs, and constraints:

• Input: A singly linked list represented by its head node
• Output: The head of the reversed linked list
• Constraints:
  • Each node has a value and a next pointer
  • The list can have 0 to n nodes (where n is the number of nodes)
  • We're guaranteed valid input structure

Assumptions I'm making:

• The linked list is singly-linked (no prev pointers)
• We can modify the structure in-place
• The solution should return a new head pointing to the reversed list

Data shape and hidden structure: The problem involves a linear data structure where each node points to the next node in sequence. The "hidden" structure is that we're essentially reorganizing the directional flow of pointers from left-to-right to right-to-left while maintaining all node values intact.

The problem is about pointer manipulation rather than value swapping, which makes it fundamentally different from array reversal where we can swap elements in place.

2. Pattern Recognition

The problem asks us to reverse a singly linked list, which is a classic pattern that appears frequently in coding interviews and real-world systems design.

Most likely patterns:

1. Linked List Traversal with Pointer Manipulation - The core operation involves traversing nodes while re-linking them in reverse order
2. Three-Pointer Technique - We need to maintain references to previous, current, and next nodes simultaneously
3. Iterative List Reversal - This is a fundamental algorithm pattern for list manipulation

Wording that signals the pattern:

• "Reverse" - clearly indicates we need to change the direction of links
• "Singly linked list" - tells us we have a linear structure with single-direction pointers
• "Return the new head" - suggests we're transforming the structure rather than just returning values

Why this fits the pattern: This is a canonical linked list reversal problem where we must:

• Change the direction of pointers from current.next = next to next.next = current
• Maintain proper traversal through the list
• Handle the head pointer transition correctly

Core insight: The key insight is that we need to keep track of three consecutive nodes at any time: the previous node (to which we'll point), the current node (which we're processing), and the next node (to preserve reference before breaking the link). This three-pointer approach prevents losing references during the reversal process.

This pattern appears in many variations:

• Reverse linked list in groups of k nodes
• Reverse linked list recursively vs iteratively
• Reverse doubly linked lists with bidirectional pointers

The fundamental structure is always the same: maintain proper node references while changing link directions.

3. Approach Evolution

My first instinct is to think about how I would reverse a linked list by hand - I'd need to change the direction of all the pointers. The most straightforward approach would be to iterate through the list and reverse the links one by one, but that's O(n²) if I'm not careful about tracking the previous node. Let me think about how to optimize this.

The key insight is that I need to maintain three pointers at each step: the previous node, current node, and next node. This way I can reverse one link at a time without losing track of the remaining list.

I notice that if I maintain the invariant that I always have access to the previous node and current node, I can reduce it to O(n) by processing each node exactly once. The tricky part is handling the pointer reassignment carefully to avoid losing references.

Let me walk through this more systematically:

First, I'll consider a brute force approach where I collect all values and then reconstruct the list in reverse order. This would be O(n) time but O(n) space, which isn't optimal.

Then I'll think about the iterative approach where I maintain three pointers: previous, current, and next. At each step, I'll save the next node, reverse the current link to point to previous, then move all pointers forward.

The improvement comes from avoiding extra space usage and processing each node only once. The key optimization is to think of this as a three-pointer sliding window that moves through the list, maintaining the correct links throughout.

Final approach: Use three pointers (prev, current, next) to iterate through the list once. At each step, I save the next node before modifying the current node's pointer, then advance all pointers forward.

Important invariants that must hold:

1. At any point, prev is the node that should come after current in the reversed list
2. Current is the node we're currently processing
3. Next is the original next node that we need to preserve for the next iteration
4. The current node's pointer should point to prev after processing
5. We never lose access to nodes that still need to be processed

This approach is optimal because it uses constant extra space and processes each node exactly once.

4. Data Structure Choice

For reversing a linked list, the primary data structure is the singly linked list itself, which consists of nodes with a val field and a next pointer.

Why Each Data Structure Is Needed

Linked List Nodes: Each node contains:

• val: The value stored in the node
• next: Pointer to the next node in the sequence

The linked list structure is essential because:

• It's the input and output format
• We need to manipulate pointers between nodes
• The reversal operation fundamentally changes pointer directions

Temporary Variables: We use a few temporary variables to manage the pointer transitions:

• prev: Points to the previous node (initially null)
• current: Points to the current node being processed
• next: Temporarily stores the next node before we lose reference to it

Time and Space Impact

Time Complexity:

• O(1) for each pointer manipulation operation
• O(n) overall for processing all n nodes

Space Complexity:

• O(1) extra space (only using a constant number of variables)
• No additional data structures like arrays or hash maps needed

Helper Structure for Implementation

We don't need any additional helper data structures beyond the basic linked list node structure. The algorithm uses an iterative approach that only requires three pointers to be tracked simultaneously, making it very memory-efficient.

The simplicity of using just the existing linked list structure with three pointer variables makes this approach optimal for both time and space complexity. The solution doesn't require any additional collections or data structures beyond what's inherent to the problem definition.

// The approach uses only the existing linked list node structure
// with three pointer variables: prev, current, and next

5. Algorithm Walkthrough

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

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

Step-by-step execution:

1. Initialization:

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

2. First iteration (current = 1 -> 2 -> 3 -> 4 -> null):

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

3. Second iteration (current = 2 -> 3 -> 4 -> null):

   • Save next node: next = 3 -> 4 -> null
   • Reverse the link: 2 -> 1 -> null
   • Move pointers: prev = 2 -> 1 -> null, current = 3 -> 4 -> null

4. Third iteration (current = 3 -> 4 -> null):

   • Save next node: next = 4 -> null
   • Reverse the link: 3 -> 2 -> 1 -> null
   • Move pointers: prev = 3 -> 2 -> 1 -> null, current = 4 -> null

5. Fourth iteration (current = 4 -> null):

   • Save next node: next = null
   • Reverse the link: 4 -> 3 -> 2 -> 1 -> null
   • Move pointers: prev = 4 -> 3 -> 2 -> 1 -> null, current = null

6. Termination:

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

Edge case handling:

• Empty list (null input) → returns null immediately
• Single node list (1 -> null) → first iteration sets 1 -> null, returns 1 -> null

The algorithm correctly handles all cases by maintaining the invariant that prev always points to the already-reversed portion of the list, and current points to the remaining nodes yet to be processed.

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 for iterative reversal
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;
        
        while (current != null) {
            // Store the next node before breaking the link
            next = current.next;
            
            // Reverse the link
            current.next = prev;
            
            // Move pointers forward
            prev = current;
            current = next;
        }
        
        // prev is now the new head of the reversed list
        return prev;
    }
}

This solution uses the classic three-pointer technique for iterative linked list reversal. It maintains references to the previous node, current node, and next node during traversal to properly reverse the links without losing access to subsequent nodes. The algorithm handles all edge cases including 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) for each of the n nodes. Since we visit each node only once and perform O(1) work per node, the total time complexity is O(n).

Space Complexity: O(1)

The space complexity is constant because we only use a fixed number of pointer variables (prev, current, next) regardless of the input list size. We don't use any additional data structures that grow with input size - we're simply reusing the existing node references to rearrange the links. The algorithm modifies the list in-place without requiring any auxiliary space beyond a few temporary variables.

Why these bounds are correct:

The O(n) time bound is tight because we must examine every node at least once to reverse the links properly. There's no way to reverse a linked list without visiting each node, making this bound optimal.

The O(1) space bound is tight because we're not using any recursive call stack or auxiliary data structures. The three pointers (prev, current, next) remain constant in number regardless of input size, making this space usage optimal for an iterative solution.

The solution is optimal in both time and space complexity, achieving the best possible bounds for this problem. Any algorithm that reverses a linked list must process all n nodes at least once, and the iterative approach uses minimal constant space to achieve this.

The solution is near-optimal because:

• It's linear in time, which is the best possible for this problem
• It uses constant space, which is optimal for an in-place iterative solution
• No better time or space complexity can be achieved for this problem without changing the fundamental approach

8. Edge Cases & Pitfalls

Empty List and Single Node

The most fundamental edge case is an empty list (head == null) or a single-node list. For an empty list, the result should remain null. For a single node, the head should point to itself after reversal. These cases must be handled explicitly to avoid null pointer exceptions.

Null Pointer Exceptions

When traversing the list, always check that current.next != null before accessing current.next.next. If not properly guarded, accessing a null reference will cause a runtime exception. The iterative approach must ensure proper null checks at each step.

Cycle Detection

If the input list contains a cycle (a node pointing back to a previous node in the chain), this algorithm will not terminate correctly. While the problem statement typically assumes a valid singly-linked list without cycles, it's worth noting that this solution does not detect or handle cycles.

Reference Management

When reversing the list, we must carefully manage references to avoid losing access to nodes. Specifically:

• We need to preserve the reference to the next node before changing the current node's next pointer
• If we change current.next = prev before saving the next node, we lose access to that node permanently

Loop Invariants

The algorithm maintains the invariant that:

1. prev always points to the previous node in the original list
2. current always points to the current node being processed
3. next always stores the reference to the next node before it gets overwritten

Implementation Pitfalls

Common mistakes include:

1. Not updating the prev pointer correctly in each iteration
2. Forgetting to update current = next to move to the next node in the original list
3. Incorrectly handling the initial prev value (should be null)
4. Not properly setting the new head to point to the last node in the original list

Memory Management

In languages like Java, while we don't explicitly manage memory, it's important to understand that the reversal operation doesn't create new nodes but reuses existing ones. The algorithm should not cause memory leaks or leave unreachable nodes in a way that would prevent garbage collection.

Return Value Consistency

The function must return the new head of the reversed list, which should be the original tail node. If this is not properly returned or if the return value is ignored, the reversal operation appears to succeed but the caller gets incorrect results.

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 than iterative for large lists. However, it's more intuitive and elegant in its recursive structure.

Stack-Based 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 iterative solution. It's useful for understanding the problem from a different perspective but adds unnecessary complexity.

Three-Pointer Technique (Alternative Iterative):

public ListNode reverseListThreePointer(ListNode 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 a slightly different variable naming that some find more intuitive.

The iterative approach with three pointers is preferred because it's:

• Space-efficient (O(1) space)
• Time-efficient (O(n) time)
• Easy to understand and debug
• Memory-safe for large lists

The recursive approach is more elegant but has higher space complexity due to call stack overhead, and the stack-based approach adds unnecessary complexity for this problem.

10. Test Cases

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; }
}

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
    }
}

Sample Test Cases

Test Case 1: Normal case with multiple nodes

• Input: [1,2,3,4,5]
• Expected Output: [5,4,3,2,1]
• Verification: Each node's next pointer should point to the previous node in original sequence

Test Case 2: Single node

• Input: [1]
• Expected Output: [1]
• Verification: Only one node, so no change in structure

Test Case 3: Empty list

• Input: []
• Expected Output: []
• Verification: Should return null for empty input

Test Case 4: Two nodes

• Input: [1,2]
• Expected Output: [2,1]
• Verification: First node becomes last and vice versa

Test Case 5: Duplicate values

• Input: [1,1,2,2]
• Expected Output: [2,2,1,1]
• Verification: Values are reversed in order but duplicates maintain their count

Tricky Test Case

Test Case 6: Large list with many nodes

• Input: [1,2,3,4,5,6,7,8,9,10] (10 nodes)
• Expected Output: [10,9,8,7,6,5,4,3,2,1]
• Verification: Ensures O(n) time complexity and proper pointer manipulation

Boundary Test Case

Test Case 7: Null input

• Input: null
• Expected Output: null
• Verification: Handles edge case where head is null gracefully

These test cases cover the essential scenarios including normal operation, edge cases, and boundary conditions that validate both correctness and robustness of the solution.

11. Final Summary

The core idea is to reverse a singly linked list by iteratively reorienting node pointers while maintaining references to unprocessed nodes. This solution works efficiently by using three pointers to track the previous, current, and next nodes during traversal, ensuring no node references are lost. The approach is optimal with O(n) time complexity and O(1) space complexity, making it the ideal solution for this problem where we must reverse the list in-place without additional data structures.