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

Concept Flow - Reverse a Singly Linked List Recursive

Start with head node

↓

Base case: head is None or head.next is None?

|Yes↓

Return head

No↓

Recursive call: reverse rest of list

↓

Set head.next.next = head

↓

Set head.next = None

↓

Return new head from recursion

The function calls itself on the next node until it reaches the end, then reverses the links step-by-step on the way back.

Execution Sample

DSA Rust

fn reverse_recursive(head: Option<Box<Node>>) -> Option<Box<Node>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }
    let mut head = head;
    let next = head.as_mut().unwrap().next.take();
    let new_head = reverse_recursive(next);
    head.as_mut().unwrap().next.as_mut().unwrap().next = head;
    head.as_mut().unwrap().next = None;
    new_head
}

This code reverses a singly linked list by recursively reversing the rest and then fixing the current node's next pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list 1 -> 2 -> 3 -> None	1 -> 2 -> 3 -> None	head points to 1	1 -> 2 -> 3 -> None
2	Recursive call on 2 -> 3 -> None	2 -> 3 -> None	head points to 2	2 -> 3 -> None
3	Recursive call on 3 -> None (base case)	3 -> None	head points to 3	3 -> None
4	Base case reached, return 3 -> None	3 -> None	return new_head = 3	3 -> None
5	Set 3.next = 2 (head), 2.next = None	2 -> None	3.next = 2, 2.next = None	3 -> 2 -> None
6	Return new_head = 3 -> 2 -> None	3 -> 2 -> None	return new_head	3 -> 2 -> None
7	Set 2.next.next = 1 (head), 1.next = None	1 -> None	2.next.next = 1, 1.next = None	3 -> 2 -> 1 -> None
8	Return new_head = 3 -> 2 -> 1 -> None	3 -> 2 -> 1 -> None	return new_head	3 -> 2 -> 1 -> None
9	End of recursion, reversed list returned	3 -> 2 -> 1 -> None	final head points to 3	3 -> 2 -> 1 -> None

💡 Recursion ends when head is None or head.next is None (base case reached at node 3)

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 7	Final
head	1	2	3	2	1	1
new_head	None	None	3	3	3	3
List State	1 -> 2 -> 3 -> None	2 -> 3 -> None	3 -> None	3 -> 2 -> None	3 -> 2 -> 1 -> None	3 -> 2 -> 1 -> None

Key Moments - 3 Insights

Why do we return head immediately when head.next is None?

Because this is the base case (see step 4 in execution_table), meaning we reached the last node which becomes the new head of reversed list.

Why do we set head.next.next = head after recursion?

This reverses the link by making the next node point back to current head (step 5 and 7), flipping the direction of the pointer.

Why do we set head.next = None after reversing the link?

To avoid cycles, we disconnect the original forward link from current node (step 5 and 7), making it the new tail.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is returned?

A Node with value 3

B Node with value 2

C Node with value 1

D None

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 4 where base case returns new_head = 3

At which step does the pointer 2.next.next get set to 1?

A Step 5

B Step 7

C Step 3

D Step 9

💡 Hint

Look at 'Pointer Changes' column for step 7 where 2.next.next = 1 is set

If we remove the line setting head.next = None, what happens to the list?

A List becomes empty

B List reverses correctly

C List forms a cycle causing infinite loop

D List remains unchanged

💡 Hint

Refer to key_moments about why head.next = None is needed to avoid cycles

Concept Snapshot

Reverse a singly linked list recursively:
- Base case: if head is None or head.next is None, return head
- Recursively reverse rest of list
- Set head.next.next = head to reverse link
- Set head.next = None to avoid cycle
- Return new head from recursion

Full Transcript

This concept shows how to reverse a singly linked list using recursion. The function calls itself on the next node until it reaches the last node, which becomes the new head. On returning from recursion, each node's next pointer is reversed by pointing the next node back to current node, and the current node's next pointer is set to None to avoid cycles. The final returned node is the new head of the reversed list.

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