Reverse a Singly Linked List Iterative in DSA Rust

Mental Model

We flip the direction of each arrow in the list one by one until the whole list points backward.

Analogy: Imagine a line of people holding hands forward. Reversing means each person turns around and holds the hand of the person behind them instead.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Reverse the list so it becomes 3 -> 2 -> 1 -> null

Step 1: Initialize prev as null, curr at head (1)

prev = null, curr = 1 -> 2 -> 3 -> null

Why: We start with no previous node and current at the first node to begin reversal

Step 2: Save next node (2), point curr.next to prev (null), move prev to curr (1), move curr to next (2)

1 -> null [prev]
2 -> 3 -> null [curr]

Why: Reverse first arrow and advance pointers to continue

Step 3: Save next node (3), point curr.next to prev (1), move prev to curr (2), move curr to next (3)

2 -> 1 -> null [prev]
3 -> null [curr]

Why: Reverse second arrow and move forward

Step 4: Save next node (null), point curr.next to prev (2), move prev to curr (3), move curr to next (null)

3 -> 2 -> 1 -> null [prev]
curr = null

Why: Reverse last arrow; curr is now null, reversal done

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA Rust

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

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

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

fn reverse_list(head: Option<Rc<RefCell<ListNode>>>) -> Option<Rc<RefCell<ListNode>>> {
    let mut prev: Option<Rc<RefCell<ListNode>>> = None;
    let mut curr = head;

    while let Some(node) = curr {
        let next = node.borrow_mut().next.take();
        node.borrow_mut().next = prev;
        prev = Some(node);
        curr = next;
    }
    prev
}

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

fn main() {
    let node1 = ListNode::new(1);
    let node2 = ListNode::new(2);
    let node3 = ListNode::new(3);

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());

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

    let reversed = reverse_list(Some(node1));

    println!("Reversed list:");
    print_list(&reversed);
}

while let Some(node) = curr {

loop while current node exists to process all nodes

let next = node.borrow_mut().next.take();

save next node and detach current node's next pointer

node.borrow_mut().next = prev;

reverse current node's pointer to previous node

prev = Some(node);

move prev pointer forward to current node

curr = next;

advance current pointer to next node saved earlier

Output

Original list:

1 -> 2 -> 3 -> null

Reversed list:

3 -> 2 -> 1 -> null

Complexity Analysis

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

Space: O(1) because we only use a few pointers and do not allocate extra nodes

vs Alternative: Compared to recursive reversal which uses O(n) stack space, iterative uses constant space making it more efficient for large lists

Edge Cases

empty list (head = None)

function returns None immediately without error

DSA Rust

while let Some(node) = curr {

single node list

returns the same single node as reversed list

DSA Rust

while let Some(node) = curr {

When to Use This Pattern

When you need to reverse the order of a singly linked list, use the iterative reversal pattern by flipping pointers one by one to avoid extra space.

Common Mistakes

Mistake: Not saving the next node before changing the current node's next pointer, causing loss of the rest of the list
Fix: Always save next node before reversing the pointer with next = node.next.take()

Mistake: Trying to reverse pointers without updating prev and curr correctly, causing infinite loops or incorrect links
Fix: Update prev to current node and curr to saved next node in each iteration

Summary

Reverses a singly linked list by changing the direction of each node's pointer iteratively.

Use when you want to reverse the order of nodes in a singly linked list efficiently without extra space.

The key is to save the next node before reversing the pointer and move prev and curr pointers forward step by step.

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