Reverse a Singly Linked List Iterative in DSA Rust - Build from Scratch

Reverse a Singly Linked List Iterative

📖 Scenario: You have a simple chain of connected boxes, each holding a number and a link to the next box. This is called a singly linked list. You want to flip the order of these boxes so the last one becomes the first.

🎯 Goal: Build a Rust program that creates a singly linked list, then reverses it using an iterative method, and finally prints the reversed list.

📋 What You'll Learn

Create a singly linked list with nodes containing values 1, 2, 3, 4, 5

Use an iterative method to reverse the linked list

Print the reversed linked list in the format: 5 -> 4 -> 3 -> 2 -> 1 -> None

💡 Why This Matters

🌍 Real World

Reversing linked lists is useful in many applications like undo features, navigation history, and data processing pipelines where order reversal is needed.

💼 Career

Understanding linked list reversal helps in coding interviews and building efficient data manipulation algorithms in systems programming and software development.

1

Create the singly linked list

Create a singly linked list with nodes containing values 1, 2, 3, 4, and 5. Use the struct ListNode with fields val: i32 and next: Option>. Create a variable called head that points to the first node.

DSA Rust

struct ListNode {
    val: i32,
    next: Option>,
}

fn main() {
    // Create the linked list nodes and link them
    // Your code here
}

Hint

Start by defining the ListNode struct. Then create nested Box pointers inside Some to link nodes from 1 to 5.

2

Add a variable to hold the reversed list

Create a mutable variable called prev and set it to None. This will hold the reversed list as you build it.

DSA Rust

struct ListNode {
    val: i32,
    next: Option>,
}

fn main() {
    let head = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: Some(Box::new(ListNode {
                    val: 4,
                    next: Some(Box::new(ListNode {
                        val: 5,
                        next: None,
                    })),
                })),
            })),
        })),
    }));
    // Create a mutable variable prev and set it to None
    // Your code here
}

Hint

Use let mut prev = None; to create a variable that will hold the reversed list.

3

Reverse the linked list iteratively

Use a while loop with a mutable variable current set to head. Inside the loop, save current.next in next_temp, then set current.next to prev. Update prev to current and current to next_temp. This reverses the links one by one.

DSA Rust

struct ListNode {
    val: i32,
    next: Option>,
}

fn main() {
    let head = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: Some(Box::new(ListNode {
                    val: 4,
                    next: Some(Box::new(ListNode {
                        val: 5,
                        next: None,
                    })),
                })),
            })),
        })),
    }));
    let mut prev = None;
    // Reverse the linked list iteratively
    // Your code here
}

Hint

Use while let Some(mut node) = current to loop through the list. Use node.next.take() to detach the next node safely.

4

Print the reversed linked list

Use a while loop with a variable node set to prev. Inside the loop, print node.val followed by -> . Move node to node.next. After the loop, print None.

DSA Rust

struct ListNode {
    val: i32,
    next: Option>,
}

fn main() {
    let head = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: Some(Box::new(ListNode {
                    val: 4,
                    next: Some(Box::new(ListNode {
                        val: 5,
                        next: None,
                    })),
                })),
            })),
        })),
    }));
    let mut prev = None;
    let mut current = head;
    while let Some(mut node) = current {
        let next_temp = node.next.take();
        node.next = prev;
        prev = Some(node);
        current = next_temp;
    }
    // Print the reversed linked list
    // Your code here
}

Hint

Use a while let Some(n) = node loop to print each node's value followed by -> . After the loop, print None.

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