Reverse a Singly Linked List Recursive in DSA Rust

Mental Model

We flip the direction of each link by going to the end first, then changing pointers backward as we return.

Analogy: Imagine unrolling a chain from the last link back to the first, flipping each link's direction as you go back.

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: call reverse on node 1, which calls reverse on node 2

head -> 1 -> 2 -> 3 -> null ↑ (recursion going deeper)

Why: We need to reach the last node before flipping pointers

Step 2: call reverse on node 2, which calls reverse on node 3

head -> 1 -> 2 -> 3 -> null ↑ (recursion going deeper)

Why: Keep going until the last node to start reversing

Step 3: reverse called on node 3 returns node 3 as new head

3 -> null ↑ (base case reached)

Why: Last node becomes new head of reversed list

Step 4: node 2's next (3) points back to node 2, node 2's next set to None

3 -> 2 -> null, 1 -> 2 (broken) -> null

Why: Flip pointer from 3 to 2, break old forward link

Step 5: node 1's next (2) points back to node 1, node 1's next set to None

3 -> 2 -> 1 -> null

Why: Flip pointer from 2 to 1, break old forward link

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_recursive(
    head: Option<Rc<RefCell<ListNode>>>,
) -> Option<Rc<RefCell<ListNode>>> {
    // Base case: empty or single node
    if head.is_none() || head.as_ref().unwrap().borrow().next.is_none() {
        return head;
    }

    // Recursive call on next node
    let next_node = head.as_ref().unwrap().borrow().next.clone();
    let new_head = reverse_recursive(next_node);

    // Flip the pointer of next node to point back to current
    let head_next = head.as_ref().unwrap().borrow().next.clone();
    head_next.as_ref().unwrap().borrow_mut().next = Some(head.clone());

    // Break old forward link
    head.as_ref().unwrap().borrow_mut().next = None;

    new_head
}

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

fn main() {
    // Create list 1 -> 2 -> 3 -> null
    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_head = reverse_recursive(Some(node1));

    println!("Reversed list:");
    print_list(reversed_head);
}

if head.is_none() || head.as_ref().unwrap().borrow().next.is_none() { return head; }

base case: stop recursion at empty or last node

let new_head = reverse_recursive(next_node);

recursive call to reverse rest of list

head_next.as_ref().unwrap().borrow_mut().next = Some(head.clone());

flip next node's pointer back to current node

head.as_ref().unwrap().borrow_mut().next = None;

break old forward link to avoid cycle

return new_head;

return new head of reversed list up the call stack

Output

Original list:

1 -> 2 -> 3 -> null

Reversed list:

3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once during recursion

Space: O(n) due to recursion call stack for n nodes

vs Alternative: Iterative reversal uses O(1) space but recursive is simpler to write and understand

Edge Cases

empty list

returns None immediately without recursion

DSA Rust

if head.is_none() || head.as_ref().unwrap().borrow().next.is_none() { return head; }

single node list

returns the single node as is without changes

DSA Rust

if head.is_none() || head.as_ref().unwrap().borrow().next.is_none() { return head; }

When to Use This Pattern

When you see a problem asking to reverse a linked list recursively, use the pattern of going to the end first then flipping pointers on the way back.

Common Mistakes

Mistake: Not breaking the old forward link causing cycles
Fix: Set current node's next pointer to None after flipping the next node's pointer back

Mistake: Returning the wrong node as new head
Fix: Always return the new head from the deepest recursive call

Summary

Reverses a singly linked list by recursively flipping pointers from the end back to the start.

Use when you want a clean recursive solution to reverse a linked list.

The key insight is to reverse the rest of the list first, then flip the current node's pointer backward.

Practice

1. What is the main idea behind reversing a singly linked list using recursion?

easy

A. Reverse the rest of the list first, then adjust the current node's next pointer

B. Swap the values of the first and last nodes only

C. Iterate through the list and reverse pointers in a loop

D. Create a new list and copy elements in reverse order

Solution

1. Step 1: Understand recursive reversal logic

   In recursion, we reverse the list starting from the end by calling the function on the next node first.

2. Step 2: Adjust pointers after recursion returns

   After the recursive call returns, we set the next node's next pointer to the current node, effectively reversing the link.

3. Final Answer:

   Reverse the rest of the list first, then adjust the current node's next pointer -> Option A

4. Quick Check:

   Recursive reversal = reverse rest first [OK]

Hint: Think: reverse tail first, then fix current link [OK]

Common Mistakes:

• Trying to swap node values instead of pointers
• Reversing pointers before recursive call
• Using iteration instead of recursion

2. Which of the following Rust function signatures correctly represents a recursive function to reverse a singly linked list?

easy

A. fn reverse_list(head: Node) -> Node

B. fn reverse_list(head: &mut Node) -> &mut Node

C. fn reverse_list(head: Option) -> Option

D. fn reverse_list(head: &Node) -> Node

Solution

1. Step 1: Identify correct ownership and return type

   In Rust, linked lists use Option to represent nullable pointers with ownership.

2. Step 2: Match function signature for recursive reversal

   The function should take ownership of the list head and return the new head after reversal, so Option input and output is correct.

3. Final Answer:

   fn reverse_list(head: Option) -> Option -> Option C

4. Quick Check:

   Ownership with Option = fn reverse_list(head: Option) -> Option [OK]

Hint: Use Option for linked list nodes in Rust [OK]

Common Mistakes:

• Using references without ownership causing borrow errors
• Returning plain Node instead of Option
• Passing mutable references incorrectly

3. Given the following Rust code snippet for recursive reversal, what will be the output list after reversal if the input list is 1 -> 2 -> 3 -> null?

fn reverse_list(head: Option) -> Option {
    match head {
        None => None,
        Some(mut node) => {
            if node.next.is_none() {
                Some(node)
            } else {
                let next = node.next.take();
                let new_head = reverse_list(next);
                let mut tail = new_head.as_ref();
                while let Some(t) = tail {
                    if t.next.is_none() {
                        break;
                    }
                    tail = t.next.as_ref();
                }
                tail.unwrap().next = Some(node);
                node.next = None;
                new_head
            }
        }
    }
}

medium

A. 3 -> 2 -> 1 -> null

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

C. 2 -> 3 -> 1 -> null

D. Compile-time error due to borrowing

Solution

1. Step 1: Analyze pointer manipulation and borrowing

   The code tries to get a mutable reference to tail via as_ref() and then mutate tail.unwrap().next, which causes a borrowing error in Rust.

2. Step 2: Understand Rust's borrowing rules

   Rust does not allow mutable access through an immutable reference (as_ref()), so this code will cause a compile-time error.

3. Final Answer:

   Compile-time error due to borrowing -> Option D

4. Quick Check:

   Immutable ref then mutable write = error [OK]

Hint: Check mutable vs immutable references in Rust code [OK]

Common Mistakes:

• Ignoring Rust's strict borrowing rules
• Assuming as_ref() allows mutation
• Not using take() properly to avoid borrow conflicts

4. Identify the bug in this recursive Rust function to reverse a singly linked list:

fn reverse_list(head: Option) -> Option {
    match head {
        None => None,
        Some(mut node) => {
            if node.next.is_none() {
                Some(node)
            } else {
                let next = node.next.take();
                let new_head = reverse_list(next);
                node.next.as_mut().unwrap().next = Some(node);
                node.next = None;
                new_head
            }
        }
    }
}

medium

A. Function does not return the new head

B. Using node.next.as_mut().unwrap() after take() causes None unwrap panic

C. Missing base case for empty list

D. No bug, code is correct

Solution

1. Step 1: Understand effect of take() on node.next

   Calling node.next.take() sets node.next to None, so node.next.as_mut() returns None.

2. Step 2: Identify unsafe unwrap causing panic

   Calling unwrap() on None causes a runtime panic, so node.next.as_mut().unwrap() is invalid after take().

3. Final Answer:

   Using node.next.as_mut().unwrap() after take() causes None unwrap panic -> Option B

4. Quick Check:

   unwrap on None after take() = panic [OK]

Hint: Don't unwrap after take() without checking for None [OK]

Common Mistakes:

• Assuming node.next still exists after take()
• Ignoring unwrap panic possibility
• Not returning new_head properly

5. You want to reverse a singly linked list recursively in Rust, but also count how many nodes were reversed. Which approach correctly combines reversal and counting? Options: A) Modify the recursive function to return a tuple (new_head, count) and increment count after each recursion. B) Use a global mutable variable to count nodes during recursion. C) Reverse the list first, then iterate again to count nodes. D) Count nodes before reversal and ignore during recursion.

hard

A. Modify the recursive function to return a tuple (new_head, count) and increment count after each recursion.

B. Use a global mutable variable to count nodes during recursion.

C. Reverse the list first, then iterate again to count nodes.

D. Count nodes before reversal and ignore during recursion.

Solution

1. Step 1: Combine reversal and counting in recursion

   Modify the recursive function to return both the new head and the count of nodes reversed as a tuple.

2. Step 2: Increment count after each recursive call

   Each recursive call returns the count from deeper calls; add 1 for the current node before returning.

3. Final Answer:

   Modify the recursive function to return a tuple (new_head, count) and increment count after each recursion. -> Option A

4. Quick Check:

   Return tuple (head, count) in recursion = Modify the recursive function to return a tuple (new_head, count) and increment count after each recursion. [OK]

Hint: Return (head, count) tuple from recursion to track nodes [OK]

Common Mistakes:

• Using global variables causing unsafe code
• Counting nodes separately after reversal wastes time
• Ignoring counting during recursion