Reverse a linked list

You're deep into your Amazon interview when the interviewer draws a series of boxes connected by arrows on the whiteboard. "Let's say you have a train of cargo containers," they begin, "and you need to reverse the entire train so it goes in the opposite direction. How would you do it?" This real-world analogy perfectly captures one of the most fundamental linked list operations - reversing a linked list. It's a problem that tests your understanding of pointer manipulation and in-place algorithms, making it a favorite at companies like Amazon, Apple, and Oracle.

TL;DR

Reverse a singly linked list in-place using three pointers: previous, current, and next. At each node, save the next reference, redirect the current node's pointer to previous, then advance both pointers forward. This runs in O(n) time and O(1) space. The critical step is saving iterator.next before overwriting it, otherwise you lose access to the rest of the list. Return the previous pointer when traversal ends, as it points to the new head.

Why This Problem Matters

Reversing a linked list is the "Hello World" of linked list manipulation. I've seen this problem used as a warm-up in countless interviews, and for good reason. It tests whether you truly understand how linked lists work under the hood. Master this, and you'll have the foundation to tackle more complex linked list problems like detecting cycles, finding intersections, or implementing LRU caches.

Linked Lists: A Quick Refresher

Before we dive into reversing, let's ensure we're on the same page about linked lists. Unlike arrays where elements sit next to each other in memory, linked lists are like a treasure hunt - each node contains data and a clue (pointer) to find the next treasure.

Key characteristics of singly linked lists:

• Nodes: Each element contains data and a reference to the next node
• Head: The first node in the list
• Tail: The last node, which points to null
• Sequential Access: You must traverse from the head to reach any element

Think of it like a conga line at a party - each person (node) holds onto the person in front of them (next pointer), and you can only join at the back or leave from the front.

Understanding the Problem

Let's break down what we're being asked to do:

Given: A head node of a singly linked list Task: Reverse the list in-place Return: The new head of the reversed list Constraint: Use O(1) space (modify the existing nodes, don't create new ones)

Here's the transformation we need to achieve:

After reversal:

The key insight here is that we're not just reversing the values - we're reversing the actual links between nodes. Node 2, which previously pointed to node 3, should now point to node 1.

Edge Cases to Consider

1. Empty list (null head): Should return null
2. Single node: Already reversed, return as-is
3. Two nodes: Simple swap of direction
4. Large lists: Our algorithm should handle any size efficiently

Solution Approach

Let's think about this problem step by step. If you had to physically reverse a train of cargo containers, you might:

1. Detach each container one by one from the front
2. Reattach it to form a new train in reverse order
3. Keep track of which container becomes the new front

This is exactly what we'll do with our linked list!

The Intuitive Approach

Imagine you're reversing the direction of a one-way street. You need to:

1. Go to each intersection (node)
2. Change the direction sign (next pointer)
3. Keep track of where you came from (previous node)
4. Move to the next intersection

This naturally leads us to the three-pointer technique:

• Previous: Where we came from (initially null)
• Current: Where we are now (starts at head)
• Next: Where we're going (temporary storage)

Pro tip: Drawing this out during your interview shows clear thinking and helps catch errors before you code.

Building the Algorithm

Let's trace through the reversal of [1, 2, 3]:

Initial State:

Step 1: Reverse first link

• Save next (node 2)
• Point 1 to previous (null)
• Move forward

Step 2: Reverse second link

• Save next (node 3)
• Point 2 to previous (node 1)
• Move forward

Step 3: Reverse final link

• Save next (null)
• Point 3 to previous (node 2)
• We're done!

Implementation

Here's our solution with detailed explanations:

public class Solution {
  public ListNode reverseList(ListNode head) {
    // Initialize our three pointers
    ListNode iterator = head;    // Current node we're processing
    ListNode previous = null;    // Node that will follow current after reversal

    // Process each node in the original list
    while (iterator != null) {
      // Step 1: Save the next node before we break the link
      ListNode nextNode = iterator.next;

      // Step 2: Reverse the current node's pointer
      iterator.next = previous;

      // Step 3: Move previous forward to current node
      previous = iterator;

      // Step 4: Move iterator forward to the saved next node
      iterator = nextNode;
    }

    // When iterator becomes null, previous is at the old tail (new head)
    return previous;
  }
}

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

Iteration 1:

• iterator = 1, previous = null
• Save nextNode = 2
• Set 1.next = null
• Move: previous = 1, iterator = 2

Iteration 2:

• iterator = 2, previous = 1
• Save nextNode = 3
• Set 2.next = 1
• Move: previous = 2, iterator = 3

This continues until we've reversed all links!

Visual Step-by-Step

Let me show you exactly how the pointers move through the list:

Initial: previous at null, iterator at 1

After first iteration: 1 points to null

After second iteration: 2 points to 1

Complexity Analysis

Time Complexity: O(n)

We visit each node exactly once to reverse its pointer. Whether the list has 5 nodes or 5 million, we perform a constant amount of work per node:

• Save next reference: O(1)
• Reverse pointer: O(1)
• Update variables: O(1)

Total: O(n) where n is the number of nodes.

Space Complexity: O(1)

This is the beauty of the iterative approach - we only use three pointer variables regardless of list size. We're modifying the existing nodes in-place rather than creating new ones.

I've seen candidates try recursive solutions, which work but use O(n) space due to the call stack. In interviews, mentioning this trade-off shows good engineering judgment.

Alternative Approaches

1. Recursive Approach: Elegant but uses O(n) stack space
2. Stack-based: Push all nodes then pop to rebuild - uses O(n) extra space
3. Creating new list: Build reversed list with new nodes - uses O(n) extra space

Our iterative approach is optimal for both time and space!

Common Pitfalls

Having interviewed hundreds of candidates, here are the most common mistakes I see:

1. Losing the next node: Forgetting to save iterator.next before overwriting it

   // Wrong!
   iterator.next = previous;  // Lost reference to rest of list!
   iterator = iterator.next;  // Now iterator is previous!
   

2. Returning the wrong node: Returning head (which is now the tail) instead of previous

   // Wrong!
   return head;  // This is now the last node!
   // Correct:
   return previous;  // This is the new head
   

3. Off-by-one errors: Not handling the last node correctly

4. Null pointer exceptions: Not checking if the list is empty

Pro tip: Always trace through your algorithm with a simple example (like [1, 2, 3]) before coding. It catches 90% of logic errors!

Interview Tips

When solving this problem in an interview:

1. Start with clarifying questions:

   • "Should I modify the existing list or create a new one?"
   • "How should I handle an empty list?"
   • "Is this a singly or doubly linked list?"

2. Draw the picture:

   • Sketch the initial list
   • Show how pointers will move
   • Visualize the final state

3. Explain your approach:

   • "I'll use three pointers to reverse links as I traverse"
   • "This gives us O(n) time and O(1) space"
   • "Let me trace through a simple example..."

4. Consider follow-ups:

   • "How would you reverse only part of the list?"
   • "What if this was a doubly linked list?"
   • "Can you do this recursively?"

5. If you get stuck:

   • Go back to the drawing
   • Think about the simplest case (2 nodes)
   • Remember: you're just changing what each node points to

Key Takeaway

💡 The essence of reversing a linked list is the three-pointer dance: save the next, reverse the current, move forward. Master this pattern - it appears in many linked list problems!

Real-World Applications

You might wonder when you'd actually need to reverse a linked list. Here are some practical scenarios:

1. Undo operations: Maintaining a history of actions in reverse chronological order
2. Blockchain: Each block points to the previous one - reversing gives chronological order
3. Browser history: Implementing back/forward navigation
4. Call stacks: Function calls are naturally in reverse order of completion

Key Takeaways

• The iterative three-pointer technique (previous, current, next) reverses a linked list in O(n) time and O(1) space, making it the optimal solution for 2026 interviews.
• Always save iterator.next before overwriting the pointer; losing this reference is the most common bug candidates introduce.
• Return previous (not head) at the end, because previous points to the old tail which is now the new head of the reversed list.
• The recursive approach is elegant but uses O(n) call stack space; mention this tradeoff to demonstrate engineering judgment.
• Test with three edge cases: empty list (null), single node, and two nodes. These catch null pointer exceptions and off-by-one errors before they reach the interviewer.

Practice Makes Perfect

Reversing a linked list is just the beginning of your linked list journey. Once you've mastered this, try these related problems:

• Reverse a linked list in groups of K
• Check if a linked list is a palindrome (hint: reverse half of it!)
• Reverse nodes between positions M and N
• Reverse every alternate K nodes

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job at a FAANG company, mastering fundamentals like this will set you up for success.

Happy coding, and may all your pointers point in the right direction! 🔄