If you've spent any time prepping for technical interviews, you've probably seen "Reverse a Linked List" on a list of must-know problems. It seems trivial at first glance—just flip the arrows, right? But when you're standing at a whiteboard with a marker in your hand, it's surprisingly easy to accidentally orphan your entire data structure and create a massive memory leak.

The Temptation of the Extra Buffer

When I first encountered this problem years ago, my instinct was to play it safe. I thought, "Why struggle with pointer manipulation when I can just store everything in a std::vector or a std::stack?" The logic is seductive: push every node pointer onto a stack, then pop them off one by one to rebuild the list in reverse order. It's intuitive because it treats the linked list like a sequence we can just "undo."

The problem is that this approach completely defeats the purpose of using a linked list. Linked lists are chosen when we want to avoid the contiguous memory requirements of an array. If you allocate a vector to hold 10,000 node pointers just to reverse the list, you've suddenly turned an $O(1)$ space problem into an $O(n)$ space problem. You're trading memory efficiency for a slightly simpler mental model, and in a production environment with massive datasets, that trade-off is usually a non-starter.

The Three-Pointer Dance

The "right" way to do this—the way that will actually impress a senior engineer—is to do it in-place. The trick is realizing that you can't just change a node's next pointer to point backward, because the moment you do, you lose the reference to the rest of the list. You've effectively cut the chain and thrown the rest of it into the void.

To solve this, we need to maintain three pointers simultaneously: where we are (curr), where we've been (prev), and where we're going (next). I like to think of it as a sliding window of three nodes. You save the "future" node, flip the current node's pointer to the "past," and then slide the whole window forward one step. It feels like a bit of a shell game, but it's the only way to ensure no node is ever left stranded.

struct Node {
    int data;
    Node* next;
};

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    Node* next = nullptr;

    while (curr != nullptr) {
        // 1. Save the next node (don't lose the rest of the list!)
        next = curr->next; 
        
        // 2. Reverse the actual pointer
        curr->next = prev; 
        
        // 3. Move the window forward
        prev = curr;
        curr = next;
    }
    // prev ends up as the new head
    return prev;
}

Why the In-Place Logic Wins

When you compare these two, the time complexity is identical—both are $O(n)$ because you have to touch every node exactly once. But the space complexity is where the real winner emerges. The in-place version uses a constant amount of extra memory regardless of whether the list has five nodes or five million.

Beyond the big-O notation, there's a cache locality argument here. By modifying the pointers in-place, you're working with the memory you already have. Allocating a separate container forces the OS to find new heap space, which is significantly slower than just flipping a few bits of address data in existing nodes. It's the difference between reorganizing the books on a shelf and buying a second shelf just to move the books in a different order.

📋 Practical Task

Exercise: Implementing a Non-Recursive In-Place List Reversal

Write a C++ function Node* reverseLinkedList(Node* head) that reverses a singly linked list in-place. Your implementation must not use any auxiliary data structures (no vectors, stacks, or recursion) to ensure $O(1)$ space complexity.

• Create a simple Node struct with an integer data and a Node* next pointer.
• Implement the reversal logic using the three-pointer approach.
• Test your function by creating a list (e.g., 1 → 2 → 3 → 4), reversing it, and printing the resulting list to verify it is now (4 → 3 → 2 → 1).
• Ensure that the original head of the list is correctly handled and the new head is returned.