Reverse a Doubly Linked List in DSA Rust

Mental Model

To reverse a doubly linked list, we swap the previous and next links of each node, then move forward using the old next pointer until all nodes are reversed.

Analogy: Imagine walking backward on a path where each step has a sign pointing forward and backward. To reverse the path, you swap the directions on each sign and then follow the new directions to the end.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, reverse the list

Goal: Reverse the doubly linked list so that the head becomes the tail and all links are reversed

Step 1: Start at head node 1, swap its prev and next pointers

null ← 1 ← null  2 ↔ 3 -> null
↑curr=1

Why: Swapping prev and next reverses the direction of links for node 1

Step 2: Move curr to old next node 2 (which is now prev after swap)

null ← 1 ← null  2 ↔ 3 -> null
     ↑curr=2

Why: We use the old next pointer saved in prev to continue reversing

Step 3: Swap prev and next pointers of node 2

null ← 1 ← null  2 ← 3 -> null
     ↑curr=2

Why: Reverse links for node 2 to point backward

Step 4: Move curr to old next node 3 (now prev after swap)

null ← 1 ← null  2 ← 3 -> null
          ↑curr=3

Why: Continue reversing by moving to next node

Step 5: Swap prev and next pointers of node 3

null ← 1 ← null  2 ← 3 ← null
          ↑curr=3

Why: Reverse links for last node 3

Step 6: Move curr to old next which is null, stop and update head to node 3

null ← 3 ↔ 2 ↔ 1 -> null
↑head=3

Why: Reversal complete, new head is last node processed

Result:

null ← 3 ↔ 2 ↔ 1 -> null
head points to 3

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    val: i32,
    prev: Option<Rc<RefCell<Node>>>,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, prev: None, next: None }))
    }
}

fn print_list(head: Option<Rc<RefCell<Node>>>) {
    let mut curr = head;
    while let Some(node) = curr {
        print!("{}", node.borrow().val);
        curr = node.borrow().next.clone();
        if curr.is_some() {
            print!(" ↔ ");
        }
    }
    println!(" -> null");
}

fn reverse_doubly_linked_list(head: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
    let mut curr = head;
    let mut new_head = None;

    while let Some(node_rc) = curr {
        let mut node = node_rc.borrow_mut();
        // Swap prev and next pointers
        let temp = node.prev.take();
        node.prev = node.next.take();
        node.next = temp;

        // Move curr to old next which is now prev
        curr = node.prev.clone();

        // Update new_head to current node
        new_head = Some(node_rc.clone());
    }

    new_head
}

fn main() {
    // Create nodes
    let node1 = Node::new(1);
    let node2 = Node::new(2);
    let node3 = Node::new(3);

    // Connect nodes 1 <-> 2 <-> 3
    {
        let mut n1 = node1.borrow_mut();
        n1.next = Some(node2.clone());
    }
    {
        let mut n2 = node2.borrow_mut();
        n2.prev = Some(node1.clone());
        n2.next = Some(node3.clone());
    }
    {
        let mut n3 = node3.borrow_mut();
        n3.prev = Some(node2.clone());
    }

    println!("Original list:");
    print_list(Some(node1.clone()));

    let reversed_head = reverse_doubly_linked_list(Some(node1));

    println!("Reversed list:");
    print_list(reversed_head);
}

let temp = node.prev.take();

temporarily store prev pointer before swap

node.prev = node.next.take();

swap prev with next pointer

node.next = temp;

complete swap by assigning old prev to next

curr = node.prev.clone();

move curr to old next node (now prev after swap) to continue reversal

new_head = Some(node_rc.clone());

update new head to current node after swap

Output

Original list:

1 ↔ 2 ↔ 3 -> null

Reversed list:

3 ↔ 2 ↔ 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once to swap pointers

Space: O(1) because reversal is done in place without extra data structures

vs Alternative: Compared to creating a new reversed list, this in-place reversal saves space and is more efficient

Edge Cases

empty list (head is None)

function returns None immediately without error

DSA Rust

while let Some(node_rc) = curr {

single node list

prev and next swap but remain None, list stays same but reversed correctly

DSA Rust

let temp = node.prev.take();

When to Use This Pattern

When you see a problem asking to reverse a doubly linked list, reach for pointer swapping of prev and next links because it reverses direction in place efficiently.

Common Mistakes

Mistake: Moving curr to node.next after swapping pointers instead of old next saved in prev
Fix: Move curr to node.prev after swap because prev holds old next pointer

Mistake: Not updating the new head after reversal
Fix: Keep track of last processed node as new head to return correct reversed list

Summary

Reverses a doubly linked list by swapping prev and next pointers of each node.

Use when you need to reverse the order of nodes in a doubly linked list efficiently.

The key insight is swapping prev and next pointers and moving forward using the old next pointer stored in prev.

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