Reverse a Doubly Linked List | Multiple Approaches

Reversing a doubly linked list (DLL) involves transforming its structural pointers so that the list flows in the exact opposite direction. This chapter explores two primary solution strategies: a naive data-swapping approach using an auxiliary stack ($O(N)$ space) and an optimal pointer-reversal approach ($O(1)$ space).

1. Problem Statement & Conceptual Overview

Given the head of a doubly linked list, the objective is to reverse the list in place (or by modifying its elements) and return the new head of the reversed list.

Unlike a singly linked list where nodes only have a next pointer, a doubly linked list contains both next and back (or previous) pointers. When reversed, every node's forward and backward directions are swapped.

2. Naive Approach: Data Swapping Using a Stack

The Core Idea

Instead of modifying the complex web of memory pointers right away, the brute-force approach ignores the structural links and simply swaps the data values inside the nodes.

Why Use a Stack?

A stack is a Last-In-First-Out (LIFO) data structure. By pushing data elements into a stack during a forward traversal and popping them out during a second traversal, the elements naturally emerge in reverse order.

Step-by-Step Execution

1. Pass 1 (Push to Stack): Initialize a temporary pointer at the head. Traverse the entire DLL, pushing every node's data into an auxiliary stack until the temporary pointer hits null.
2. Pass 2 (Pop & Replace): Reset the temporary pointer back to the head. Traverse the DLL a second time, taking the top element from the stack, replacing the current node's data with it, popping from the stack, and advancing the temporary pointer.

Pseudocode Implementation

// Step 1: Push all node data into the stack
Stack<Integer> stack = new Stack<>();
Node temp = head;

while (temp != null) {
    stack.push(temp.data);
    temp = temp.next;
}

// Step 2: Pop from stack and overwrite node data
temp = head;
while (temp != null) {
    temp.data = stack.pop();
    temp = temp.next;
}

Complexity Analysis

• Time Complexity: $O(2N) \approx O(N)$ because the algorithm requires two full traversals of the linked list (one for pushing, one for popping).
• Space Complexity: $O(N)$ because an external stack data structure is required to store all $N$ data values.

3. The Optimal Approach: Single-Pass Link Reversal

Interviewers will reject the two-pass data-swapping approach due to its $O(N)$ auxiliary space overhead and because it fails to actually restructure the pointers. The optimal solution requires a single-pass pointer reversal running in $O(N)$ time and $O(1)$ space.

Real-Life Analogy: Reversing Train Car Connections

Think of a doubly linked list like a train where each carriage is rigidly coupled to both the carriage ahead of it and the carriage behind it.

• In the naive approach, you would run through the train, pick up the passengers/cargo from each car, and swap them around.
• In the optimal approach, you uncouple and swap the front and rear connectors of every single car while walking down the train once, completely reversing the direction of travel without moving a single passenger.

4. Mental Model: Swapping Pointers for a Single Node

Let us isolate a single node inside a doubly linked list. Before reversal, it points to a next node and a back (previous) node.

To swap two variables (a and b) in programming, we use a temporary variable:

temp = a;
a = b;
b = temp;

We apply this exact variable-swapping logic to a node's pointers (back and next), ensuring we do not lose reference to adjacent nodes during the overwrite.

5. Step-by-Step Pointer Manipulation

To perform the link reversal cleanly across the entire list during a single traversal, we maintain a current pointer and a last (representing the previous node processed) pointer.

For every node encountered:

1. Store the old back pointer: last = current.back
2. Swap the back pointer: current.back = current.next
3. Swap the next pointer: current.next = last
4. Advance the traversal: Move to the next node by stepping backwards along the newly oriented structure: current = current.back

Visual Walkthrough of Iterations

6. Complete Production-Ready Code (C++)

Here is the complete, optimized implementation that handles base cases (empty lists or single-element lists) and executes the pointer reversal in $O(1)$ auxiliary space.

/**
 * Definition for doubly linked list.
 * struct Node {
 *     int data;
 *     Node* next;
 *     Node* back;
 *     Node(int val) : data(val), next(nullptr), back(nullptr) {}
 * };
 */

Node* reverseDLL(Node* head) {
    // Base case: If the list is empty or has only one node, 
    // it is already reversed.
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    Node* prev = nullptr;
    Node* current = head;
    
    // Traverse the list and swap pointers for every node
    while (current != nullptr) {
        // Step 1: Remember the current back pointer
        prev = current->back;
        
        // Step 2: Swap the back pointer with the next pointer
        current->back = current->next;
        
        // Step 3: Assign the stored back pointer to next
        current->next = prev;
        
        // Step 4: Move to the next node in the original order 
        // (which is now stored in current->back)
        current = current->back;
    }
    
    // When current becomes null, 'prev' is pointing to the 
    // second-to-last node, whose 'back' pointer now holds 
    // the new head of the reversed list.
    return prev->back;
}

7. Complexity Comparison Summary

Summary and Key Takeaways

• Understand the Dual-Pointer Structure: Doubly linked lists maintain bidirectional traversal via both next and back pointers.
• Avoid Data Swapping in Interviews: Data-swapping with stacks is inefficient ($O(N)$ space) and fails to demonstrate structural pointer manipulation skills.
• The Swap Pattern: Reversing links requires a temporary reference (analogous to swapping two variables) to prevent memory loss when reassigning pointers.
• Single-Pass Traversal: By updating current->back and current->next simultaneously, you can invert the list in a single traversal.
• Advancing via back: Because pointers are reversed as you move forward, the traversal step must advance using current = current->back.
• New Head Location: Upon loop termination (current == null), the new head of the doubly linked list resides at prev->back.
• Base Case Vigilance: Always check for empty lists (head == nullptr) or single-node lists (head->next == nullptr) to prevent segmentation faults.
• Communicate the Intuition: In technical interviews, explain the single-node isolation and variable-swapping intuition before diving into code implementation.