Reverse a Doubly Linked List in DSA Rust - 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?

DSA Rust

struct Node {
    data: i32,
    prev: Option<Box<Node>>,
    next: Option<Box<Node>>,
}

// Simplified representation for this example
// Original list: 1 <-> 2 <-> 3 <-> null
// After reverse, what is the list?

fn main() {
    let mut list = vec![1, 2, 3];
    list.reverse();
    for val in list {
        print!("{} <-> ", val);
    }
    print!("null");
}

A 3 <-> 2 <-> 1 <-> null

B 1 <-> 2 <-> 3 <-> null

C null <-> 3 <-> 2 <-> 1

D 3 -> 2 -> 1 -> null

💡 Hint

Think about how reversing changes the order of elements in the list.

Reversing the list changes the order from 1, 2, 3 to 3, 2, 1. The doubly linked list uses <-> to show links in both directions, so the output shows the reversed order with arrows pointing both ways.

🧠 Conceptual

intermediate

Understanding pointers in doubly linked list reversal

When reversing a doubly linked list, which pointers must be swapped for each node?

A Only the prev pointer

B Neither pointer needs to be swapped

C Only the next pointer

D Both prev and next pointers

💡 Hint

Think about how the direction of links changes when reversing.

In a doubly linked list, each node has two pointers: prev and next. To reverse the list, you must swap these pointers for every node so that the direction of traversal is reversed.

🔧 Debug

advanced

Identify the error in this doubly linked list reversal code

What error will this Rust code produce when trying to reverse a doubly linked list?

DSA Rust

fn reverse(mut head: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut current = head;
    while let Some(mut node) = current {
        let temp = node.next;
        node.next = node.prev;
        node.prev = temp;
        current = node.prev;
    }
    head
}

A Compilation error due to moving out of borrowed content

B Null pointer dereference

C Infinite loop at runtime

D No error, code runs correctly

💡 Hint

Look at how ownership and borrowing rules apply when accessing node fields.

The code tries to move out of node.next and node.prev while node is borrowed, which Rust does not allow. This causes a compilation error about moving out of borrowed content.

🚀 Application

advanced

Resulting list after reversing a complex doubly linked list

Given a doubly linked list with nodes containing values [10, 20, 30, 40], what is the printed list after reversing?

DSA Rust

let mut list = vec![10, 20, 30, 40];
list.reverse();
for val in list {
    print!("{} <-> ", val);
}
print!("null");

A 10 <-> 20 <-> 30 <-> 40 <-> null

B 40 <-> 30 <-> 20 <-> 10 <-> null

C null <-> 40 <-> 30 <-> 20 <-> 10

D 40 -> 30 -> 20 -> 10 -> null

💡 Hint

Reversing changes the order from first to last to last to first.

The list is reversed, so the order becomes 40, 30, 20, 10. The doubly linked list notation uses <-> to show links in both directions.

❓ Predict Output

expert

Output after reversing a doubly linked list with one node

What is the output of the following Rust code that reverses a doubly linked list with a single node?

DSA Rust

struct Node {
    data: i32,
    prev: Option<Box<Node>>,
    next: Option<Box<Node>>,
}

fn main() {
    let mut list = vec![42];
    list.reverse();
    for val in list {
        print!("{} <-> ", val);
    }
    print!("null");
}

A 42 -> null

B null

C 42 <-> null

D null <-> 42

💡 Hint

Reversing a single element list keeps it the same.

A list with one node reversed remains the same. The output shows the node value followed by <-> null indicating the end of the list.

Practice

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

easy

A. To change the order of nodes so the last becomes first and vice versa

B. To delete all nodes from the list

C. To add new nodes at the end of the list

D. To sort the nodes in ascending order

Solution

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

   A doubly linked list has nodes connected both forward and backward.

2. Step 2: Purpose of reversing

   Reversing swaps the direction so the last node becomes the first and the first becomes the last.

3. Final Answer:

   To change the order of nodes so the last becomes first and vice versa -> Option A

4. Quick Check:

   Reversing means flipping order = C [OK]

Hint: Reversing flips the list order front to back [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Mixing up adding nodes with reversing

2. Which Rust code snippet correctly swaps the next and prev pointers of a node in a doubly linked list?

easy

A. let temp = node.prev; node.prev = node.next; node.next = temp.next;

B. node.next = node.next; node.prev = node.prev;

C. node.prev = node.next; node.next = node.prev;

D. let temp = node.next; node.next = node.prev; node.prev = temp;

Solution

1. Step 1: Identify correct swapping logic

   Swapping means storing one pointer temporarily, then exchanging values.

2. Step 2: Check each option

   let temp = node.next; node.next = node.prev; node.prev = temp; correctly uses a temp variable to swap next and prev. Others either assign incorrectly or use wrong variables.

3. Final Answer:

   let temp = node.next; node.next = node.prev; node.prev = temp; -> Option D

4. Quick Check:

   Swap pointers with temp variable = D [OK]

Hint: Use a temp variable to swap pointers safely [OK]

Common Mistakes:

• Assigning pointers without temp causes data loss
• Mixing up next and prev in assignments
• Using wrong pointer in swap

3. Given the Rust code below that reverses a doubly linked list, what will be the printed output?

struct Node {
    data: i32,
    prev: Option,
    next: Option,
}

// Assume list is 1 <-> 2 <-> 3
// After reversal, print from head

// Output format: data values separated by spaces

// Output?

medium

A. 3 2 1

B. 1 2 3

C. 2 3 1

D. 3 1 2

Solution

1. Step 1: Understand initial list order

   The list is 1 <-> 2 <-> 3, so printing from head gives 1 2 3.

2. Step 2: Effect of reversal

   Reversing swaps next and prev pointers, so the new head is 3, and order is 3 2 1.

3. Final Answer:

   3 2 1 -> Option A

4. Quick Check:

   Reversed list prints backwards = 3 2 1 [OK]

Hint: Reversed doubly linked list prints nodes backward [OK]

Common Mistakes:

• Printing original order after reversal
• Confusing node data order
• Assuming reversal sorts nodes

4. Identify the bug in this Rust function that attempts to reverse a doubly linked list:

fn reverse(mut head: Option) -> Option {
    let mut current = head;
    while let Some(mut node) = current {
        let temp = node.next;
        node.next = node.prev;
        node.prev = temp;
        current = node.next;
    }
    head
}

medium

A. The loop condition should be while current.is_some()

B. Swapping next and prev pointers is done incorrectly

C. The function does not update head to the new first node after reversal

D. The function should return current instead of head

Solution

1. Step 1: Analyze pointer swapping

   Swapping next and prev is done correctly inside the loop.

2. Step 2: Check head update

   The function returns original head without updating it to the new first node after reversal, so head remains old start.

3. Final Answer:

   The function does not update head to the new first node after reversal -> Option C

4. Quick Check:

   Head must point to new first node after reverse = A [OK]

Hint: Update head to last processed node after reversal [OK]

Common Mistakes:

• Not updating head pointer after reversal
• Returning old head instead of new head
• Incorrect loop condition causing infinite loop

5. You have a doubly linked list with nodes containing integers. After reversing it, you want to find the sum of all nodes that were originally at even positions (2nd, 4th, etc.). Which approach correctly solves this in Rust?

hard

A. Reverse the list, then traverse and sum nodes at odd positions in the reversed list

B. Traverse original list, sum nodes at even positions, then reverse the list

C. Reverse the list, then sum all nodes without position checks

D. Traverse reversed list and sum nodes at even positions

Solution

1. Step 1: Understand position change after reversal

   Reversing changes node positions, so original even positions become different in reversed list.

2. Step 2: Correct approach

   Sum nodes at even positions before reversal to get original even-position sum, then reverse list if needed.

3. Final Answer:

   Traverse original list, sum nodes at even positions, then reverse the list -> Option B

4. Quick Check:

   Sum original even positions before reversing = A [OK]

Hint: Sum before reversing to keep original positions intact [OK]

Common Mistakes:

• Summing positions after reversal which changes order
• Ignoring position changes due to reversal
• Summing all nodes without filtering positions