Reverse a Singly Linked List Iterative in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of reversing a linked list with 3 nodes

What is the printed state of the linked list after reversing it iteratively?

DSA Rust

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
};

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

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

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

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

A 1 -> null

B 3 -> 2 -> 1 -> null

C null

D 1 -> 2 -> 3 -> null

💡 Hint

Trace the pointers step-by-step to see how the links reverse.

The iterative reversal changes the next pointers so the list order reverses. Starting from 1->2->3->null, after reversal it becomes 3->2->1->null.

❓ Predict Output

intermediate

Output when reversing an empty linked list

What is the printed output after reversing an empty linked list iteratively?

DSA Rust

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
};

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

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

fn main() {
    let head: Option<Box<ListNode>> = None;
    let reversed_head = reverse_list(head);
    print_list(&reversed_head);
}

A null

B 0 -> null

C Error: NoneType dereference

D Empty list

💡 Hint

Consider what happens when the input list is empty.

Reversing an empty list returns None, so printing it results in just 'null'.

🔧 Debug

advanced

Identify the error in this iterative reversal code

What error will this code cause when reversing a linked list?

DSA Rust

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
};

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

A Null pointer dereference

B Stack overflow due to infinite loop

C No error, runs correctly

D Use of moved value: current.next

💡 Hint

Check how ownership and moves are handled in Rust when accessing current.next.

The code tries to use current.next after moving current out of head without taking ownership properly, causing a use of moved value error.

❓ Predict Output

advanced

Final list after reversing a 5-node linked list

What is the printed linked list after reversing this 5-node list iteratively?

DSA Rust

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
};

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

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

fn main() {
    let mut head = None;
    for i in (1..=5).rev() {
        head = Some(Box::new(ListNode { val: i, next: head }));
    }
    let reversed_head = reverse_list(head);
    print_list(&reversed_head);
}

A 5 -> 4 -> 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> 4 -> 5 -> null

C null

D 1 -> null

💡 Hint

Check how the list is constructed before reversal and what reversal does.

The list is constructed as 1->2->3->4->5->null using the reversed iterator. After reversal, it becomes 5->4->3->2->1->null.

🧠 Conceptual

expert

Why is iterative reversal preferred over recursive for large linked lists?

Which reason best explains why iterative reversal is preferred over recursive reversal for very large singly linked lists?

A Iterative reversal is easier to write and understand for beginners.

B Recursive reversal is faster due to compiler optimizations.

C Iterative reversal uses constant extra memory, avoiding stack overflow risks.

D Recursive reversal cannot reverse lists with cycles.

💡 Hint

Think about memory usage and call stack limits.

Recursive reversal uses call stack frames proportional to list size, risking stack overflow. Iterative reversal uses a few pointers and constant memory.

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