Reverse a Doubly Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of reversing a doubly linked list

What is the printed state of the doubly linked list after reversing it using the given code?

DSA C++

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

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

// Initial list: 1 <-> 2 <-> 3 <-> 4 <-> nullptr
// After reverse, print from head to end: data -> ... -> nullptr

A nullptr

B 1 -> 2 -> 3 -> 4 -> nullptr

C 4 -> 3 -> 2 -> 1 -> nullptr

D 4 -> 3 -> 2 -> nullptr

💡 Hint

Think about how the pointers are swapped and how the head is updated after reversal.

The code swaps the prev and next pointers for each node, effectively reversing the list. The new head is the last node processed, which is node with data 4. So the list prints as 4 -> 3 -> 2 -> 1 -> nullptr.

🧠 Conceptual

intermediate

Understanding pointer swaps in reversing doubly linked list

In the reversal process of a doubly linked list, which pointers are swapped for each node?

A Only next pointers are swapped for each node

B prev and next pointers are swapped for each node

C Only prev pointers are swapped for each node

D prev pointers are set to nullptr and next pointers remain unchanged

💡 Hint

Think about how the direction of the list is reversed.

Reversing a doubly linked list requires swapping both prev and next pointers for each node to reverse the direction of links.

🔧 Debug

advanced

Identify the error in this reverse function

What error will occur when running this reverse function on a doubly linked list?

DSA C++

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

A The loop will run infinitely causing a runtime error

B The function will cause a segmentation fault due to null pointer dereference

C The function will reverse correctly without errors

D The function will return the original head without reversing

💡 Hint

Check how the current pointer moves inside the loop.

The line 'current = current->next;' is incorrect because after swapping prev and next, current->next points to the old prev (nullptr for head), causing the loop to exit after one iteration without processing the rest of the list. Thus, it returns the original head without reversing.

❓ Predict Output

advanced

Resulting list after partial reversal

Given a doubly linked list 1 <-> 2 <-> 3 <-> 4 <-> 5, what is the printed list after reversing only the first three nodes using the code below?

DSA C++

Node* partialReverse(Node* head, int k) {
    Node* current = head;
    Node* temp = nullptr;
    int count = 0;
    while (current != nullptr && count < k) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
        count++;
    }
    if (temp != nullptr) {
        head = temp->prev;
    }
    return head;
}

// Print list from returned head to end

A 3 -> 2 -> 1 -> nullptr

B 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

C 3 -> 2 -> 1 -> 4 -> 5 -> nullptr

D 5 -> 4 -> 3 -> 2 -> 1 -> nullptr

💡 Hint

Only the first k nodes are reversed, the rest remain in original order.

The first three nodes are reversed, so the head becomes node 3, followed by 2 and 1. The code does not connect 1's next to 4, so printing from head shows 3 -> 2 -> 1 -> nullptr.

🧠 Conceptual

expert

Time complexity of reversing a doubly linked list

What is the time complexity of reversing a doubly linked list with n nodes by swapping pointers in a single pass?

A O(n)

B O(1)

C O(log n)

D O(n^2)

💡 Hint

Consider how many nodes are visited and how many operations per node.

Reversing the list requires visiting each node once and swapping pointers, so the time complexity is linear, O(n).

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