Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Reversing a Doubly Linked List

MEDIUMProblemSolveExternal Links

Description

You are given the head of a doubly linked list. Each node in this list has three fields: a data value, a next pointer pointing to the following node, and a prev pointer pointing to the preceding node.

Your task is to reverse the doubly linked list in-place so that the first node becomes the last, the second node becomes the second-to-last, and so on. After reversal, return the new head of the reversed list.

A doubly linked list differs from a singly linked list in that each node maintains a pointer to both its successor and its predecessor. This bidirectional linkage means that reversing the list requires swapping both the next and prev pointers for every node.

Examples

Example 1

Input: head = 3 <-> 4 <-> 5

Output: 5 <-> 4 <-> 3

Explanation: The original list starts at node 3 and ends at node 5. After reversal, node 5 becomes the new head. Node 4 stays in the middle but its prev and next pointers are swapped. Node 3 becomes the tail, with its next pointing to null. Every node's prev and next pointers have been swapped.

Example 2

Input: head = 75 <-> 122 <-> 59 <-> 196

Output: 196 <-> 59 <-> 122 <-> 75

Explanation: The original list has four nodes. After reversal, the last node 196 becomes the new head and the first node 75 becomes the tail. The order is completely flipped while maintaining valid doubly-linked connections in both directions.

Example 3

Input: head = 10

Output: 10

Explanation: A single node list is already reversed. Its prev and next pointers are both null, and reversing them changes nothing.

Constraints

  • 1 ≤ number of nodes ≤ 10^6
  • 0 ≤ node.data ≤ 10^4

Editorial

Brute Force

Intuition

The simplest way to think about reversing a doubly linked list is: what if we just collected all the values, reversed the collection, and then wrote them back into the nodes?

Imagine you have a row of numbered boxes connected by ropes in both directions. Instead of re-tying the ropes, you could write down all the numbers on a notepad, flip the notepad upside-down, and then write the numbers back into the boxes in the new order.

This approach uses a stack (Last-In, First-Out data structure). We traverse the entire list from head to tail, pushing each node's value onto a stack. Since a stack reverses order naturally — the last value pushed is the first one popped — we then traverse the list again from head to tail, replacing each node's data with the value popped from the stack.

This effectively reverses the data without touching any pointers.

Step-by-Step Explanation

Let's trace through with head = 3 <-> 4 <-> 5:

Phase 1 — Push all values onto a stack:

Step 1: Start at head node with value 3. Push 3 onto the stack. Stack: [3].

Step 2: Move to the next node with value 4. Push 4 onto the stack. Stack: [3, 4].

Step 3: Move to the next node with value 5. Push 5 onto the stack. Stack: [3, 4, 5]. We've reached the end of the list.

Phase 2 — Pop values back into the list:

Step 4: Start again at head node (value 3). Pop from stack → 5. Replace node's data: 3 becomes 5. Stack: [3, 4].

Step 5: Move to the next node (value 4). Pop from stack → 4. Replace node's data: 4 stays 4. Stack: [3].

Step 6: Move to the next node (value 5). Pop from stack → 3. Replace node's data: 5 becomes 3. Stack: [].

Result: The list is now 5 <-> 4 <-> 3. The data has been reversed, although the pointer structure is unchanged.

Stack-Based Reversal — Push Values Then Pop Back — Watch how we collect all node values into a stack, then pop them back in reverse order to overwrite each node's data.

Algorithm

  1. Create an empty stack
  2. Traverse the doubly linked list from head to tail:
    • Push each node's data value onto the stack
  3. Traverse the list again from head to tail:
    • Pop the top value from the stack
    • Replace the current node's data with the popped value
  4. Return the head (pointer structure unchanged, data reversed)

Code

class Solution {
public:
    Node* reverseDLL(Node* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        
        stack<int> st;
        Node* temp = head;
        
        // Push all values onto stack
        while (temp != nullptr) {
            st.push(temp->data);
            temp = temp->next;
        }
        
        // Pop values back into the list
        temp = head;
        while (temp != nullptr) {
            temp->data = st.top();
            st.pop();
            temp = temp->next;
        }
        
        return head;
    }
};
class Solution:
    def reverseDLL(self, head):
        if head is None or head.next is None:
            return head
        
        stack = []
        temp = head
        
        # Push all values onto stack
        while temp is not None:
            stack.append(temp.data)
            temp = temp.next
        
        # Pop values back into the list
        temp = head
        while temp is not None:
            temp.data = stack.pop()
            temp = temp.next
        
        return head
class Solution {
    public Node reverseDLL(Node head) {
        if (head == null || head.next == null)
            return head;
        
        Stack<Integer> stack = new Stack<>();
        Node temp = head;
        
        // Push all values onto stack
        while (temp != null) {
            stack.push(temp.data);
            temp = temp.next;
        }
        
        // Pop values back into the list
        temp = head;
        while (temp != null) {
            temp.data = stack.pop();
            temp = temp.next;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list twice — once to push all n values onto the stack, and once to pop them back. Each push and pop is O(1), giving us O(n) + O(n) = O(2n), which simplifies to O(n).

Space Complexity: O(n)

The stack stores all n node values simultaneously. This extra memory is the main downside of this approach — for a list with 10^6 nodes, we use 10^6 extra space just to hold values temporarily.

Why This Approach Is Not Efficient

While the brute force achieves O(n) time, it uses O(n) extra space for the stack. With up to 10^6 nodes allowed by the constraints, this means allocating memory for a million integers just to reverse the list.

More importantly, this approach only reverses the data, not the pointers. In many real-world scenarios, other parts of the code might hold references to specific nodes. If we only swap data, those external references still point to nodes that now contain different values, which can lead to bugs.

The key insight is that a doubly linked list already gives us all the information we need to reverse it in-place. Each node has both next and prev pointers. If we simply swap these two pointers for every node, the traversal direction flips naturally. The last node (whose next was null) becomes the new head. This requires no extra data structures at all — just pointer manipulation.

Optimal Approach - Iterative Pointer Swap

Intuition

Think of a doubly linked list as a two-lane road between houses. Each house has a sign pointing to the next house on the right (the next pointer) and another sign pointing to the previous house on the left (the prev pointer).

To reverse the entire road, we don't need to physically move any houses. We just need to visit each house and swap its two directional signs — the "next" sign now points left (where "prev" used to point), and the "prev" sign now points right (where "next" used to point).

After swapping every house's signs, the road naturally flows in the opposite direction. The house that was originally at the end of the road (with its "next" sign pointing nowhere) now becomes the starting point.

The algorithm is beautifully simple:

  • Walk through each node
  • At each node, swap its next and prev pointers
  • After processing all nodes, the last node we processed becomes the new head

Because each node already stores both links, we don't need any extra data structures — we can reverse the entire list using only a temporary pointer variable.

Step-by-Step Explanation

Let's trace through with head = 3 <-> 4 <-> 5:

Initially: 3 <-> 4 <-> 5, with connections:

  • Node 3: prev=null, next=4
  • Node 4: prev=3, next=5
  • Node 5: prev=4, next=null

Step 1: Initialize prev = null, curr = head (node 3). We will traverse and swap pointers at each node.

Step 2: At node 3: Save curr.next (which is node 4) into a temp variable. Swap the pointers: set curr.next = curr.prev (null) and curr.prev = temp (node 4). Now node 3 has: prev=4, next=null. Node 3 is now effectively the tail.

Step 3: Move to the next unprocessed node. After swapping, the original "next" is now stored in curr.prev. So we set prev = curr, then curr = curr.prev (which is node 4, the original next node).

Step 4: At node 4: Save curr.next (which is node 5). Swap: curr.next = curr.prev (node 3), curr.prev = saved node 5. Now node 4 has: prev=5, next=3. The middle node's pointers are reversed.

Step 5: Move forward: prev = curr (node 4), curr = curr.prev (node 5, the original next).

Step 6: At node 5: Save curr.next (which is null). Swap: curr.next = curr.prev (node 4), curr.prev = null. Now node 5 has: prev=null, next=4. Node 5 is now the new head.

Step 7: Move forward: prev = curr (node 5), curr = curr.prev (null). curr is null, so we stop.

Step 8: The new head is prev (node 5). Return prev. The reversed list: 5 <-> 4 <-> 3.

Iterative Pointer Swap — Reversing 3 <-> 4 <-> 5 — Watch how swapping each node's next and prev pointers gradually reverses the entire doubly linked list without using extra space.

Algorithm

  1. If the list is empty or has only one node, return the head as-is
  2. Initialize two pointers: prev = null, curr = head
  3. While curr is not null:
    a. Store curr.next in a temporary variable temp
    b. Set curr.next = curr.prev (swap the forward pointer)
    c. Set curr.prev = temp (swap the backward pointer)
    d. Move prev = curr
    e. Move curr = temp (advance to the next unprocessed node)
  4. Return prev as the new head of the reversed list

Code

class Solution {
public:
    Node* reverseDLL(Node* head) {
        // Edge case: empty list or single node
        if (head == nullptr || head->next == nullptr)
            return head;
        
        Node* prev = nullptr;
        Node* curr = head;
        
        while (curr != nullptr) {
            // Save the next node before overwriting
            Node* temp = curr->next;
            
            // Swap the two pointers
            curr->next = curr->prev;
            curr->prev = temp;
            
            // Advance through the list
            prev = curr;
            curr = temp;
        }
        
        // prev now points to the new head
        return prev;
    }
};
class Solution:
    def reverseDLL(self, head):
        # Edge case: empty list or single node
        if head is None or head.next is None:
            return head
        
        prev = None
        curr = head
        
        while curr is not None:
            # Save the next node before overwriting
            temp = curr.next
            
            # Swap the two pointers
            curr.next = curr.prev
            curr.prev = temp
            
            # Advance through the list
            prev = curr
            curr = temp
        
        # prev now points to the new head
        return prev
class Solution {
    public Node reverseDLL(Node head) {
        // Edge case: empty list or single node
        if (head == null || head.next == null)
            return head;
        
        Node prev = null;
        Node curr = head;
        
        while (curr != null) {
            // Save the next node before overwriting
            Node temp = curr.next;
            
            // Swap the two pointers
            curr.next = curr.prev;
            curr.prev = temp;
            
            // Advance through the list
            prev = curr;
            curr = temp;
        }
        
        // prev now points to the new head
        return prev;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list exactly once, visiting each of the n nodes one time. At each node we perform a constant number of pointer operations (save, swap next, swap prev, advance). Total work: n × O(1) = O(n).

Space Complexity: O(1)

We only use three pointer variables (prev, curr, temp) regardless of the list size. No additional data structures are allocated. This is a significant improvement over the brute force approach which needed O(n) stack space.