Reverse a Singly Linked List Iterative in DSA Rust - Execution Trace

Concept Flow - Reverse a Singly Linked List Iterative

Start with head node

↓

Initialize prev = None, current = head

↓

Loop while current != None

↓

Save next = current.next

↓

Reverse pointer: current.next = prev

↓

Move prev = current

↓

Move current = next

↓

Loop ends when current == None

↓

Return prev as new head

We start from the head and move through the list, reversing each node's pointer to the previous node until we reach the end. The previous pointer becomes the new head.

Execution Sample

DSA Rust

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

This Rust function reverses a singly linked list by iteratively changing the next pointers of each node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize prev=None, current=head (1->2->3->None)	1->2->3->None	prev=None, current=1	1 -> 2 -> 3 -> None
2	Save next=2, reverse 1.next=None, move prev=1, current=2	1->None, 2->3->None	1.next=None, prev=1, current=2	1 -> None, 2 -> 3 -> None
3	Save next=3, reverse 2.next=1, move prev=2, current=3	1->None, 2->1->None, 3->None	2.next=1, prev=2, current=3	2 -> 1 -> None, 3 -> None
4	Save next=None, reverse 3.next=2, move prev=3, current=None	3->2->1->None	3.next=2, prev=3, current=None	3 -> 2 -> 1 -> None
5	Loop ends, return prev as new head	3->2->1->None	Return prev=3	3 -> 2 -> 1 -> None

💡 current becomes None, loop ends, prev is new head of reversed list

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
prev	None	1->None	2->1->None	3->2->1->None	3->2->1->None
current	1->2->3->None	2->3->None	3->None	None	None
next	N/A	2->3->None	3->None	None	None

Key Moments - 3 Insights

Why do we set current.next = prev instead of prev.next = current?

Because we want to reverse the direction of the current node's pointer to point backward. Setting current.next = prev changes the link from forward to backward. This is shown in execution_table steps 2, 3, and 4 where current.next is updated.

What happens to the original next pointer of the current node?

We save it in 'next' before changing current.next. This prevents losing access to the rest of the list. See execution_table step 2 where next=2 is saved before reversing pointers.

Why does the loop stop when current is None?

Because current being None means we have processed all nodes. At this point, prev points to the new head of the reversed list. This is shown in execution_table step 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the visual state of the list?

A 1 -> 2 -> 3 -> None

B 3 -> 2 -> 1 -> None

C 2 -> 1 -> None, 3 -> None

D 1 -> None, 2 -> 3 -> None

💡 Hint

Check the 'Visual State' column at step 3 in the execution_table.

At which step does the current pointer become None?

A Step 4

B Step 3

C Step 5

D Step 2

💡 Hint

Look at the 'Pointer Changes' column to see when current becomes None.

If we forget to save 'next' before reversing pointers, what happens?

A The list reverses correctly

B We lose access to the rest of the list after current node

C The loop never ends

D prev remains None

💡 Hint

Refer to key_moments about saving 'next' before changing current.next.

Concept Snapshot

Reverse a singly linked list iteratively:
- Use two pointers: prev (start None) and current (start head)
- Loop while current is not None:
  - Save next = current.next
  - Set current.next = prev (reverse link)
  - Move prev = current, current = next
- Return prev as new head
This reverses the list in O(n) time and O(1) space.

Full Transcript

To reverse a singly linked list iteratively, we start with two pointers: prev set to None and current set to the head of the list. We loop through the list while current is not None. In each iteration, we save the next node to not lose the rest of the list. Then, we reverse the current node's pointer to point to prev. We move prev to current and current to the saved next node. When current becomes None, prev points to the new head of the reversed list. This process reverses the list in linear time without extra space.

Practice

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

easy

A. To change the direction of the links so the last node becomes the first

B. To sort the linked list in ascending order

C. To remove duplicate nodes from the list

D. To find the middle node of the list

Solution

1. Step 1: Understand the linked list structure

   A singly linked list has nodes pointing only to the next node, so reversing means changing these pointers.

2. Step 2: Identify the effect of reversal

   Reversing changes the direction so the last node points to null and becomes the new head.

3. Final Answer:

   To change the direction of the links so the last node becomes the first -> Option A

4. Quick Check:

   Reversing = changing link directions [OK]

Hint: Reversing flips links, last node becomes first [OK]

Common Mistakes:

• Confusing reversal with sorting
• Thinking reversal removes nodes
• Assuming reversal finds middle node

2. Which of the following Rust code snippets correctly initializes a mutable pointer for reversing a singly linked list iteratively?

easy

A. let mut prev = Some(Node::new());

B. let prev = Some(Node::new());

C. let mut prev = None;

D. let prev = None;

Solution

1. Step 1: Understand pointer initialization for reversal

   We start with a previous pointer set to None because initially no nodes are reversed.

2. Step 2: Check mutability and value

   We need mutable prev to update it during iteration, so 'let mut prev = None;' is correct.

3. Final Answer:

   let mut prev = None; -> Option C

4. Quick Check:

   Mutable prev starts as None [OK]

Hint: Start prev as mutable None to track reversed list [OK]

Common Mistakes:

• Forgetting mut keyword
• Initializing prev with a new node incorrectly
• Using immutable prev when mutation is needed

3. Given the following Rust code snippet for reversing a singly linked list iteratively, what will be the printed output after reversal?

struct Node {
    val: i32,
    next: Option,
}

fn print_list(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.val);
        current = &node.next;
    }
    println!("null");
}

fn reverse_list(mut head: Option) -> Option {
    let mut prev = None;
    while let Some(mut current) = head {
        head = current.next.take();
        current.next = prev;
        prev = Some(current);
    }
    prev
}

fn main() {
    let node3 = Node { val: 3, next: None };
    let node2 = Node { val: 2, next: Some(Box::new(node3)) };
    let node1 = Node { val: 1, next: Some(Box::new(node2)) };
    let head = Some(Box::new(node1));

    let reversed_head = reverse_list(head);
    print_list(&reversed_head);
}

medium

A. null

B. 1 -> 2 -> 3 -> null

C. Compilation error

D. 3 -> 2 -> 1 -> null

Solution

1. Step 1: Trace the reversal process

   The list starts as 1 -> 2 -> 3 -> null. The reversal changes links so the last node (3) becomes head.

2. Step 2: Confirm print output after reversal

   After reversal, print_list prints nodes from new head: 3 -> 2 -> 1 -> null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option D

4. Quick Check:

   Reversed list prints in reverse order [OK]

Hint: Reversed list prints nodes in reverse order [OK]

Common Mistakes:

• Assuming list prints original order after reversal
• Confusing Option C null with empty list
• Thinking code causes compilation error

4. Identify the error in the following Rust code snippet for reversing a singly linked list iteratively:

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

medium

A. prev should be immutable

B. Missing .take() when assigning head = current.next

C. Loop condition should be while head.is_some()

D. Function should return head instead of prev

Solution

1. Step 1: Understand ownership in Rust linked list

   current.next is an Option, but to move it out, .take() is needed to avoid borrowing errors.

2. Step 2: Identify the error in head assignment

   head = current.next; tries to move without .take(), causing ownership error. Correct is head = current.next.take();

3. Final Answer:

   Missing .take() when assigning head = current.next -> Option B

4. Quick Check:

   Use .take() to move ownership safely [OK]

Hint: Use .take() to move Option ownership in Rust [OK]

Common Mistakes:

• Ignoring Rust ownership rules
• Making prev immutable by mistake
• Changing loop condition unnecessarily

5. You have a singly linked list with nodes containing integer values. You want to reverse the list iteratively and then remove all nodes with even values from the reversed list. Which approach correctly combines these two operations in Rust?

hard

A. First reverse the list iteratively, then iterate over reversed list to filter out even nodes by rebuilding a new list

B. Filter out even nodes first, then reverse the filtered list recursively

C. Reverse the list recursively and remove even nodes during reversal by skipping them

D. Use a stack to push all nodes, pop them to reverse, and skip even nodes while popping

Solution

1. Step 1: Reverse the list iteratively

   Use the iterative reversal method to get the reversed list with all nodes.

2. Step 2: Filter out even nodes from reversed list

   Iterate over reversed list and build a new list skipping nodes with even values.

3. Final Answer:

   First reverse the list iteratively, then iterate over reversed list to filter out even nodes by rebuilding a new list -> Option A

4. Quick Check:

   Reverse then filter by rebuilding list [OK]

Hint: Reverse first, then filter by rebuilding list [OK]

Common Mistakes:

• Trying to filter during reversal causing complexity
• Using recursion when iterative is required
• Using stack unnecessarily increasing space