Reverse a Doubly Linked List in DSA C++ - Deep Dive

Overview - Reverse a Doubly Linked List

What is it?

A doubly linked list is a chain of nodes where each node points to both its previous and next node. Reversing it means changing the direction so the last node becomes the first, and all links flip accordingly. This operation rearranges the list without creating new nodes. It helps us traverse the list backward easily after reversal.

Why it matters

Reversing a doubly linked list is important because it allows us to change the order of elements efficiently without extra memory. Without this, we would need to create a new list or use extra space to reverse data, which is slower and uses more memory. This operation is common in undo features, navigation history, and many algorithms that require backward traversal.

Where it fits

Before learning this, you should understand what a doubly linked list is and how nodes connect with previous and next pointers. After mastering reversal, you can explore more complex list operations like sorting, merging, or implementing advanced data structures like dequeues or LRU caches.

Mental Model

Core Idea

Reversing a doubly linked list means swapping each node's previous and next links so the list direction flips end-to-start.

Think of it like...

Imagine a two-way street where cars can go forward or backward. Reversing the list is like flipping all the street signs so cars now drive in the opposite direction on the same road.

Original list:
Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail

After reversal:
Tail ⇄ Node3 ⇄ Node2 ⇄ Node1 ⇄ Head

Build-Up - 6 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn how each node in a doubly linked list connects to both previous and next nodes.

A doubly linked list node has three parts: data, a pointer to the previous node, and a pointer to the next node. The first node's previous pointer is null, and the last node's next pointer is null. This allows traversal forward and backward.

Result

You can move through the list from head to tail and tail to head using next and previous pointers.

Understanding the two-way connections is essential because reversing the list means swapping these pointers for every node.

2

Foundation

Traversing a Doubly Linked List

Concept: Learn how to move through the list using next and previous pointers.

Starting from the head, follow the next pointers to reach the tail. Similarly, from the tail, follow previous pointers to go back to the head. This confirms the list's bidirectional nature.

Result

You can print or access nodes in both forward and backward order.

Knowing traversal directions helps visualize what reversal will change: the direction of these pointers.

3

Intermediate

Swapping Previous and Next Pointers

🤔Before reading on: Do you think swapping previous and next pointers for each node will reverse the list direction? Commit to yes or no.

Concept: Reversing the list means swapping the previous and next pointers in every node.

For each node, store its next pointer temporarily. Then set its next pointer to its previous pointer, and its previous pointer to the stored next pointer. Move to the original next node and repeat until all nodes are processed.

Result

All nodes have their previous and next pointers swapped, effectively reversing the list direction.

Swapping pointers in place avoids creating new nodes or lists, making reversal efficient in time and space.

4

Intermediate

Updating the Head Pointer After Reversal

🤔Before reading on: After swapping pointers, should the head pointer move to the original tail or stay the same? Commit to your answer.

Concept: After reversing pointers, the head pointer must update to the original tail node.

While swapping pointers, keep track of the last processed node. After the loop, set the head pointer to this node because it becomes the new start of the reversed list.

Result

The head pointer correctly points to the new first node after reversal.

Failing to update the head pointer leaves the list inaccessible or incorrectly ordered.

5

Advanced

Complete C++ Code for Reversal

🤔Before reading on: Predict the output of reversing the list 1 ⇄ 2 ⇄ 3. Commit to your answer.

Concept: Implement the reversal logic in C++ with proper pointer swaps and head update.

struct Node { int data; Node* prev; Node* next; }; Node* reverseDoublyLinkedList(Node* head) { Node* current = head; Node* temp = nullptr; while (current != nullptr) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } if (temp != nullptr) { head = temp->prev; } return head; } // Example usage: // List: 1 ⇄ 2 ⇄ 3 // After reversal: 3 ⇄ 2 ⇄ 1

Result

Reversed list: 3 ⇄ 2 ⇄ 1

Seeing the full code ties together pointer swaps and head update, showing a practical, runnable solution.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think reversing an empty or single-node list changes anything? Commit to yes or no.

Concept: Consider empty lists and single-node lists, and analyze time complexity.

If the list is empty (head is null) or has one node, reversal does nothing and returns the same head. The reversal runs in O(n) time, where n is the number of nodes, because each node is visited once. No extra memory is used, so space complexity is O(1).

Result

Reversal handles all list sizes safely and efficiently.

Recognizing edge cases prevents bugs in real systems; understanding complexity helps optimize performance.

Under the Hood

Each node stores two pointers: prev and next. Reversal swaps these pointers for every node. Internally, this changes the direction of links so traversal order flips. The head pointer updates to the last node processed, which was originally the tail. This in-place pointer manipulation avoids extra memory allocation.

Why designed this way?

Doubly linked lists were designed to allow easy forward and backward traversal. Reversal by swapping pointers leverages this design to flip direction efficiently. Alternatives like creating a new reversed list waste memory and time. This method is simple, fast, and uses the existing structure.

Before reversal:
Head -> [Prev: null | Data | Next] ⇄ [Prev | Data | Next] ⇄ ... ⇄ [Prev | Data | Next: null] ← Tail

During reversal:
For each node:
  Swap Prev and Next pointers

After reversal:
New Head -> [Prev: null | Data | Next] ⇄ ... ⇄ [Prev | Data | Next: null] ← New Tail

Myth Busters - 4 Common Misconceptions

Quick: Does reversing a doubly linked list require creating new nodes? Commit yes or no.

Common Belief: Reversing a doubly linked list means making a new list with nodes in reverse order.

Reality: Reversal swaps pointers in existing nodes without creating new nodes.

Why it matters: Creating new nodes wastes memory and time, making reversal inefficient and unnecessary.

Quick: After reversal, does the head pointer stay the same? Commit yes or no.

Common Belief: The head pointer remains unchanged after reversal.

Reality: The head pointer must update to the original tail node to reflect the new start.

Why it matters: Not updating the head pointer breaks list access and traversal.

Quick: Is it enough to swap next pointers only to reverse the list? Commit yes or no.

Common Belief: Swapping only the next pointers reverses the list.

Reality: Both previous and next pointers must be swapped to maintain correct bidirectional links.

Why it matters: Swapping only one pointer breaks backward traversal and corrupts the list.

Quick: Does reversing a single-node list change its structure? Commit yes or no.

Common Belief: Reversing a single-node list changes its pointers.

Reality: A single-node list remains the same after reversal since prev and next are null.

Why it matters: Understanding this prevents unnecessary operations and confusion.

Expert Zone

1

Swapping pointers in place requires careful temporary storage to avoid losing references during the swap.

2

The reversal algorithm can be adapted to circular doubly linked lists with minor pointer adjustments.

3

In multithreaded environments, reversal must be synchronized to avoid race conditions on pointers.

When NOT to use

If you need to preserve the original list order for other operations, do not reverse in place; instead, create a reversed copy. For singly linked lists, this method does not apply; use a different reversal approach.

Production Patterns

Reversal is used in undo-redo stacks, browser history navigation, and playlist shuffling where order reversal is needed without extra memory. It also appears in algorithms that require backward iteration or reversing sequences efficiently.

Connections

Singly Linked List Reversal

Similar operation but simpler because nodes have only one pointer.

Understanding doubly linked list reversal clarifies why singly linked list reversal only swaps one pointer and requires different traversal logic.

Undo-Redo Functionality in Software

Reversal of doubly linked lists models moving backward and forward through states.

Knowing list reversal helps design efficient undo-redo stacks that navigate history in both directions.

Bidirectional Data Flow in Networking

Both involve managing two-way connections and reversing direction.

Understanding pointer swaps in lists parallels reversing data flow paths in network routing or protocols.

Common Pitfalls

#1 Not updating the head pointer after reversal.

Wrong approach:

Node* reverse(Node* head) {
Node* current = head;
Node* temp = nullptr;
while (current != nullptr) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
return head; // head not updated
}

Correct approach:

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

Root cause:

Forgetting that the head must point to the new first node after reversal.

#2 Swapping only next pointers, ignoring previous pointers.

Wrong approach:

while (current != nullptr) {
Node* nextNode = current->next;
current->next = current->prev;
current = nextNode;
}

Correct approach:

while (current != nullptr) {
Node* temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}

Root cause:

Misunderstanding that both pointers must be swapped to maintain bidirectional links.

#3 Trying to reverse an empty list without checking for null.

Wrong approach:

Node* reverse(Node* head) {
Node* current = head;
while (current->next != nullptr) { // crashes if head is null
// swap logic
}
return head;
}

Correct approach:

Node* reverse(Node* head) {
if (head == nullptr) return nullptr;
Node* current = head;
while (current != nullptr) {
// swap logic
}
return head;
}

Root cause:

Not handling the empty list case leads to runtime errors.

Key Takeaways

A doubly linked list has nodes connected both forward and backward using next and previous pointers.

Reversing the list means swapping these pointers in every node to flip the direction.

After swapping, the head pointer must update to the original tail to maintain correct access.

Reversal is done in place with O(n) time and O(1) space, making it efficient.

Handling edge cases like empty or single-node lists prevents bugs and ensures robustness.

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