Reverse a Doubly Linked List in DSA Rust - Execution Trace

Concept Flow - Reverse a Doubly Linked List

Start at head node

↓

Swap node.prev and node.next

↓

Move to node.prev (old next)

↓

Repeat until node is null

↓

Update head to last processed node

↓

Done

We start at the head, swap each node's previous and next pointers, move forward using the old next pointer, and finally update the head to the last node processed.

Execution Sample

DSA Rust

fn reverse_doubly_linked_list(head: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut current = head;
    let mut new_head = None;
    while let Some(mut node) = current {
        let next = node.next.take();
        std::mem::swap(&mut node.prev, &mut node.next);
        new_head = Some(node);
        current = next;
    }
    new_head
}

This function reverses a doubly linked list by swapping prev and next pointers of each node and returns the new head.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node 1	null	1 <-> 2 <-> 3 <-> null
2	Swap prev and next of Node 1	Node 1	prev: null -> Node 2, next: Node 2 -> null	1 <- 2 <-> 3 <-> null
3	Move to old next (Node 2)	Node 2	null	1 <- 2 <-> 3 <-> null
4	Swap prev and next of Node 2	Node 2	prev: Node 1 -> Node 3, next: Node 3 -> Node 1	1 <- 2 <- 3 <-> null
5	Move to old next (Node 3)	Node 3	null	1 <- 2 <- 3 <-> null
6	Swap prev and next of Node 3	Node 3	prev: Node 2 -> null, next: null -> Node 2	1 <- 2 <- 3
7	Move to old next (null)	null	null	3 <-> 2 <-> 1 <-> null
8	Update head to Node 3	Node 3	Head pointer updated	3 <-> 2 <-> 1 <-> null
9	End	null	Traversal complete	3 <-> 2 <-> 1 <-> null

💡 Traversal ends when current node is null after processing all nodes.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
current	Node 1	Node 2	Node 3	null	null
new_head	None	Node 1	Node 2	Node 3	Node 3
node.prev	null	Node 2	Node 3	null	null
node.next	Node 2	null	Node 1	Node 2	Node 2

Key Moments - 3 Insights

Why do we swap prev and next pointers instead of just reversing the links?

Swapping prev and next pointers (see steps 2, 4, 6) reverses the direction of the list while preserving the doubly linked structure. Simply reversing links without swapping would break the backward links.

Why do we move to node.prev after swapping instead of node.next?

After swapping, the old next pointer is now stored in node.prev (see step 3). So to move forward in the original list order, we move to node.prev.

How do we know which node becomes the new head?

The last node processed before current becomes null (step 8) is the new head, because after reversal it points to null as next.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the new prev pointer of Node 2?

A Node 3

B Node 1

C null

D Node 2

💡 Hint

Check the 'Pointer Changes' column at step 4 in the execution table.

At which step does the current pointer become null, ending the traversal?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the 'Current Node' column in the execution table to find when it becomes null.

If we forget to update the head pointer at the end, what would be the visual state?

A Original list order: 1 <-> 2 <-> 3 <-> null

B Empty list

C Reversed list but head still points to Node 1

D List with only one node

💡 Hint

Refer to step 8 where head is updated to the new head node.

Concept Snapshot

Reverse a Doubly Linked List:
- Start at head node
- For each node, swap prev and next pointers
- Move to old next node via swapped prev
- Repeat until current is null
- Update head to last processed node
- Result: list reversed with correct prev/next links

Full Transcript

To reverse a doubly linked list, we begin at the head node. For each node, we swap its prev and next pointers to reverse the direction of links. After swapping, we move to the node's old next pointer, which is now stored in prev. We continue this process until we reach the end of the list (current node becomes null). Finally, we update the head pointer to the last node processed, which becomes the new head of the reversed list. This ensures the list is reversed correctly with all backward and forward links intact.

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