Reverse a Doubly Linked List in DSA C++

Mental Model

To reverse a doubly linked list, we swap the previous and next links of each node, then update the head to the last node.

Analogy: Imagine a train with cars connected front and back. Reversing means flipping the direction of all connections so the last car becomes the first.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, reverse the list

Goal: Reverse the list so it becomes 3 ↔ 2 ↔ 1

Step 1: Start at head (node 1), swap its prev and next pointers

null ← 1 ← 2 ↔ 3 -> null
↑curr=1

Why: Swapping pointers reverses the direction for this node

Step 2: Move curr to old next (which is prev after swap), now curr=2

null ← 1 ← 2 ↔ 3 -> null
   ↑curr=2

Why: We continue reversing by moving to next node in original order

Step 3: Swap prev and next of node 2

null ← 1 ← 2 ← 3 -> null
   ↑curr=2

Why: Reverse links for node 2 to flip direction

Step 4: Move curr to old next (prev after swap), now curr=3

null ← 1 ← 2 ← 3 -> null
       ↑curr=3

Why: Continue to next node to reverse

Step 5: Swap prev and next of node 3

null ← 1 ← 2 ← 3 ← null
       ↑curr=3

Why: Reverse links for last node

Step 6: Move curr to old next (prev after swap), now curr=null, update head to last node (3)

null ← 3 ↔ 2 ↔ 1 -> null
↑head=3

Why: Reversal complete, head points to new first node

Result:

null ← 3 ↔ 2 ↔ 1 -> null
↑head=3

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    DoublyLinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }

    void reverse() {
        Node* curr = head;
        Node* temp = nullptr;
        while (curr) {
            temp = curr->prev; // store prev
            curr->prev = curr->next; // swap prev and next
            curr->next = temp;
            curr = curr->prev; // move to next node in original order
        }
        if (temp) {
            head = temp->prev; // update head to last node
        }
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            cout << temp->data;
            if (temp->next) cout << " ↔ ";
            temp = temp->next;
        }
        cout << " -> null" << endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(1);
    dll.append(2);
    dll.append(3);
    cout << "Original list:" << endl;
    dll.printList();
    dll.reverse();
    cout << "Reversed list:" << endl;
    dll.printList();
    return 0;
}

while (curr) {

iterate over each node to reverse links

temp = curr->prev; // store prev

save current prev pointer before swapping

curr->prev = curr->next; // swap prev and next

reverse the direction by swapping pointers

curr->next = temp;

complete the swap of pointers

curr = curr->prev; // move to next node in original order

advance to next node using swapped pointers

if (temp) { head = temp->prev; }

update head to new first node after reversal

Output

Original list:

1 ↔ 2 ↔ 3 -> null

Reversed list:

3 ↔ 2 ↔ 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once to swap pointers

Space: O(1) because reversal is done in place without extra storage

vs Alternative: Compared to creating a new reversed list (O(n) time and space), this in-place reversal saves memory

Edge Cases

empty list

reverse does nothing, head remains nullptr

DSA C++

while (curr) {

single node list

reverse swaps pointers but list remains same, head unchanged

DSA C++

while (curr) {

When to Use This Pattern

When you see a problem asking to reverse a doubly linked list, reach for pointer swapping of prev and next because it reverses direction in one pass.

Common Mistakes

Mistake: Not updating the head pointer after reversal
Fix: Set head to the last processed node after the loop using head = temp->prev

Mistake: Moving curr to curr->next instead of curr->prev after swapping
Fix: Move curr to curr->prev because pointers are swapped

Summary

Reverses a doubly linked list by swapping each node's prev and next pointers.

Use when you need to reverse the order of nodes in a doubly linked list efficiently.

The key insight is swapping prev and next pointers flips the list direction in one pass.

Practice

1. What is the main purpose of reversing a doubly linked list?

easy

A. To make the last node the first and the first node the last

B. To delete all nodes from the list

C. To sort the list in ascending order

D. To convert it into a singly linked list

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes with pointers to both previous and next nodes.

2. Step 2: Define reversing operation

   Reversing means swapping the direction so the last node becomes the first and vice versa.

3. Final Answer:

   To make the last node the first and the first node the last -> Option A

4. Quick Check:

   Reverse = swap start and end [OK]

Hint: Reversing swaps head and tail pointers [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Assuming it changes list type

2. Which of the following is the correct way to swap the next and prev pointers of a node curr in C++?

easy

A. curr->next = curr->prev; curr->prev = curr->next;

B. std::swap(curr->next, curr->prev);

C. curr->prev = curr->next; curr->next = curr->prev;

D. curr->next = curr->next; curr->prev = curr->prev;

Solution

1. Step 1: Understand pointer swapping

   Swapping two pointers requires a temporary storage or a swap function to avoid overwriting.

2. Step 2: Use std::swap for safe swapping

   std::swap exchanges values safely without losing data.

3. Final Answer:

   std::swap(curr->next, curr->prev); -> Option B

4. Quick Check:

   Use std::swap to exchange pointers [OK]

Hint: Use std::swap to exchange two pointers safely [OK]

Common Mistakes:

• Assigning one pointer to another without temp causes data loss
• Swapping pointers manually without temp variable
• Confusing assignment with swapping

3. What will be the output of the following code snippet after reversing the doubly linked list?

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

// List: 1 <-> 2 <-> 3
Node* head = new Node{1, nullptr, nullptr};
Node* second = new Node{2, nullptr, head};
head->next = second;
Node* third = new Node{3, nullptr, second};
second->next = third;

// Reverse function
Node* reverse(Node* head) {
  Node* curr = head;
  Node* temp = nullptr;
  while (curr != nullptr) {
    temp = curr->prev;
    curr->prev = curr->next;
    curr->next = temp;
    curr = curr->prev;
  }
  if (temp != nullptr) head = temp->prev;
  return head;
}

head = reverse(head);

// Print list
Node* tempPrint = head;
while (tempPrint != nullptr) {
  std::cout << tempPrint->data << " ";
  tempPrint = tempPrint->next;
}

medium

A. 2 3 1

B. 1 2 3

C. 3 2 1

D. 3 1 2

Solution

1. Step 1: Trace pointer swaps in reverse function

   Each node swaps its next and prev pointers, then moves to original next (now prev).

2. Step 2: Update head to new first node

   After loop, head is updated to last processed node's prev, which is the original tail.

3. Final Answer:

   3 2 1 -> Option C

4. Quick Check:

   Reversed list prints from tail to head [OK]

Hint: After reversing, head points to original tail [OK]

Common Mistakes:

• Not updating head after reversal
• Confusing next and prev pointers
• Printing from old head instead of new

4. Identify the error in the following reverse function for a doubly linked list and select the fix.

Node* reverse(Node* head) {
  Node* curr = head;
  Node* temp = nullptr;
  while (curr != nullptr) {
    temp = curr->prev;
    curr->prev = curr->next;
    curr->next = temp;
    curr = curr->next;  // Error here
  }
  if (temp != nullptr) head = temp->prev;
  return head;
}

medium

A. Change 'head = temp->prev;' to 'head = temp->next;'

B. Remove the line 'temp = curr->prev;'

C. Add 'curr = curr->prev;' before the loop

D. Change 'curr = curr->next;' to 'curr = curr->prev;'

Solution

1. Step 1: Analyze pointer movement in loop

   After swapping next and prev, moving curr to curr->next is wrong because next and prev are swapped.

2. Step 2: Correct pointer update

   We must move curr to curr->prev (original next) after swapping.

3. Final Answer:

   Change 'curr = curr->next;' to 'curr = curr->prev;' -> Option D

4. Quick Check:

   Move curr along swapped pointers [OK]

Hint: After swapping, move curr to prev pointer [OK]

Common Mistakes:

• Moving curr to next instead of prev after swap
• Not updating head correctly
• Ignoring pointer swap effects

5. Given a doubly linked list with nodes containing integers, how would you modify the reverse function to also count how many nodes were reversed and return that count along with the new head?

hard

A. Modify the function to return a pair, increment count inside the loop, and return both.

B. Add a global variable to count nodes and return only the head.

C. Count nodes before reversal and return the count without changing the function.

D. Use recursion to reverse and count nodes simultaneously without changing return type.

Solution

1. Step 1: Change function return type

   Use std::pair to return both new head and count.

2. Step 2: Count nodes during reversal

   Initialize count=0; increment count inside the reversal loop for each node processed.

3. Step 3: Return both values

   Return std::make_pair(new_head, count) after reversal completes.

4. Final Answer:

   Modify the function to return a pair, increment count inside the loop, and return both. -> Option A

5. Quick Check:

   Return both head and count using pair [OK]

Hint: Return pair with head and count, increment count in loop [OK]

Common Mistakes:

• Using global variables instead of return values
• Counting nodes before reversal only
• Trying recursion without changing return type