Reverse a Doubly Linked List in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has two links: one to the next node and one to the previous node. This allows moving forward and backward through the list.

beginner

What does reversing a doubly linked list mean?

Reversing a doubly linked list means changing the direction of all links so that the first node becomes the last, and the last node becomes the first, effectively flipping the list order.

intermediate

In Rust, what is the key step to reverse a doubly linked list?

The key step is to swap the 'next' and 'prev' pointers of each node while traversing the list, then update the head to the last processed node.

beginner

Why do we swap 'next' and 'prev' pointers when reversing a doubly linked list?

Swapping 'next' and 'prev' pointers reverses the direction of the links, so the list can be traversed in the opposite order.

beginner

What is the time complexity of reversing a doubly linked list?

The time complexity is O(n), where n is the number of nodes, because each node is visited once to swap pointers.

What pointers does each node in a doubly linked list have?

A Only next pointer

B No pointers

C Only previous pointer

D Next and previous pointers

Each node has two pointers: one to the next node and one to the previous node.

What is the first step when reversing a doubly linked list?

A Create a new list

B Delete the head node

C Swap the next and prev pointers of the current node

D Traverse to the end without changes

Swapping the next and prev pointers is the key step to reverse the list.

After reversing, what should the head pointer point to?

A The last node before reversal

B The original head node

C Null

D A new node

The head should point to the last node before reversal, which becomes the new first node.

What is the time complexity of reversing a doubly linked list?

A O(n)

B O(1)

C O(n^2)

D O(log n)

Each node is visited once, so the time complexity is linear, O(n).

Which of these is NOT true about doubly linked lists?

A Each node has two pointers

B They cannot be reversed

C They use more memory than singly linked lists

D They allow traversal in both directions

Doubly linked lists can be reversed by swapping pointers.

Explain step-by-step how to reverse a doubly linked list.

Think about what happens to the links at each node.

Describe why reversing a doubly linked list is easier than reversing a singly linked list.

Focus on the availability of backward links.

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