Reverse a Doubly Linked List in DSA C++ - Build from Scratch

Reverse a Doubly Linked List

📖 Scenario: Imagine you have a train with carriages connected in both directions. Sometimes, you want to reverse the order of the carriages so the last becomes first and the first becomes last.In programming, a doubly linked list is like this train, where each carriage (node) knows the one before and after it.

🎯 Goal: You will build a doubly linked list with exact values, then write code to reverse it so the last node becomes the first, and print the reversed list.

📋 What You'll Learn

Create a doubly linked list with nodes containing values 10, 20, 30, 40, 50 in that order

Add a pointer variable to track the head of the list

Write a function to reverse the doubly linked list by swapping next and prev pointers

Print the reversed list values from head to tail separated by spaces

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in applications like browser history navigation, music playlists, and undo-redo features where moving forward and backward is needed.

💼 Career

Understanding how to manipulate doubly linked lists is important for software engineers working on low-level data structures, performance-critical applications, and system programming.

1

Create the doubly linked list with exact nodes

Create a struct called Node with int data, Node* next, and Node* prev. Then create five nodes with values 10, 20, 30, 40, and 50 linked in order. Finally, create a Node* pointer called head pointing to the first node.

DSA C++

// Define struct Node and create nodes with values 10, 20, 30, 40, 50 linked
// Set head pointer to first node
// Your code here

Hint

Remember to link each node's next and prev pointers correctly to form the doubly linked list.

2

Add a function to reverse the doubly linked list

Add a function called reverseList that takes a Node*& head parameter. Inside, use a Node* pointer called current starting at head. Swap the next and prev pointers of each node while moving forward. After the loop, update head to the last processed node.

DSA C++

#include 
using namespace std;

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

void reverseList(Node*& head) {
    // Your code here
}

int main() {
    Node* node1 = new Node{10, nullptr, nullptr};
    Node* node2 = new Node{20, nullptr, node1};
    Node* node3 = new Node{30, nullptr, node2};
    Node* node4 = new Node{40, nullptr, node3};
    Node* node5 = new Node{50, nullptr, node4};

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    Node* head = node1;

    // Call reverseList here
    // Your code here

    return 0;
}

Hint

Swap the next and prev pointers for each node. Move current forward using the old prev pointer after swapping.

3

Print the reversed doubly linked list

Write a for loop using a Node* variable called temp starting at head. Print each node's data followed by a space until temp becomes nullptr.

DSA C++

#include 
using namespace std;

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

void reverseList(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;
    }
}

int main() {
    Node* node1 = new Node{10, nullptr, nullptr};
    Node* node2 = new Node{20, nullptr, node1};
    Node* node3 = new Node{30, nullptr, node2};
    Node* node4 = new Node{40, nullptr, node3};
    Node* node5 = new Node{50, nullptr, node4};

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    Node* head = node1;

    reverseList(head);

    for (Node* temp = head; temp != nullptr; temp = temp->next) {
        // Your code here
    }

    return 0;
}

Hint

Use a loop to move through the list from head to the end, printing each node's data followed by a space.

4

Print the reversed list output

Run the program and observe the printed output. It should show the reversed list values separated by spaces.

DSA C++

// Run the program to see the reversed list output
// Your code here

Hint

The output should be the reversed list values: 50 40 30 20 10

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