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

Concept Flow - Reverse a Singly Linked List Recursive

Start with head node

↓

Check if node is None or last node

Yes↓

Return node as new head

No↓

Recursive call on next node

↓

Reverse link: next.next = current

↓

Set current.next = None

↓

Return new head from recursion

The recursion goes to the last node, then reverses links on the way back, setting each next node to point back to current.

Execution Sample

DSA Python

def reverse_recursive(node):
    if node is None or node.next is None:
        return node
    new_head = reverse_recursive(node.next)
    node.next.next = node
    node.next = None
    return new_head

This function reverses a singly linked list by recursively reversing the rest and then fixing the current node's link.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Call reverse_recursive on node 1	1 -> 2 -> 3 -> None	None	1 -> 2 -> 3 -> None
2	Call reverse_recursive on node 2	1 -> 2 -> 3 -> None	None	1 -> 2 -> 3 -> None
3	Call reverse_recursive on node 3	1 -> 2 -> 3 -> None	None	1 -> 2 -> 3 -> None
4	Base case reached at node 3, return node 3	1 -> 2 -> 3 -> None	None	1 -> 2 -> 3 -> None
5	Reverse link: node 2.next.next = node 2	1 -> 2 -> 3 -> None	3.next = 2	1 -> 2 -> 3 -> 2 (cycle temporarily)
6	Set node 2.next = None	1 -> 2 -> None, 3 -> 2	2.next = None	1 -> 2 -> None, 3 -> 2
7	Return new head node 3	3 -> 2 -> None, 1 -> 2 (old link)	None	3 -> 2 -> None, 1 -> 2 (old link)
8	Reverse link: node 1.next.next = node 1	3 -> 2 -> None, 1 -> 2	2.next = 1	3 -> 2 -> 1
9	Set node 1.next = None	3 -> 2 -> 1 -> None	1.next = None	3 -> 2 -> 1 -> None
10	Return new head node 3	3 -> 2 -> 1 -> None	None	3 -> 2 -> 1 -> None

💡 Recursion ends when node is None or node.next is None (last node reached)

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 9	Final
node	1	2	3	3	2	1	3
new_head	None	None	3	3	3	3	3
node.next	2	3	None	None	None	None	None

Key Moments - 3 Insights

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

Because after reversing, the current node's next still points forward, causing a cycle. Setting node.next = None breaks the old forward link, as shown in steps 6 and 9.

Why does the recursion stop at node.next == None?

Because the last node has no next node, so it becomes the new head. This base case is shown in step 4 where recursion returns the last node.

How does the list look during the reversal steps?

During reversal (steps 5 and 8), links temporarily point backward creating a reversed partial list, but old forward links remain until we set node.next = None to finalize.

Visual Quiz - 3 Questions

Look at the execution table, what is the 'node' value at Step 3?

A 2

B 3

C 1

D None

💡 Hint

Check the 'node' variable in variable_tracker after Step 3

At which step does the recursion reach the base case?

A Step 4

B Step 6

C Step 2

D Step 9

💡 Hint

Look for the step where the function returns the last node without further recursion

If we forget to set node.next = None, what happens to the list?

A The list becomes empty

B The list remains unchanged

C The list has cycles causing infinite loops

D The list is reversed correctly

💡 Hint

Refer to key_moments explanation about breaking old links after reversal

Concept Snapshot

Reverse a singly linked list recursively:
- Base case: node is None or node.next is None
- Recursively reverse rest of list
- Set node.next.next = node to reverse link
- Set node.next = None to break old link
- Return new head from recursion

Full Transcript

This visualization shows how to reverse a singly linked list using recursion. The function calls itself until it reaches the last node, which becomes the new head. Then, on returning from recursion, it reverses the links by pointing the next node back to the current node and breaking the old forward link by setting current node's next to None. The execution table tracks each step, showing how the list nodes and pointers change. Key moments clarify why breaking the old link is necessary and when recursion stops. The quiz tests understanding of node values at steps, base case detection, and consequences of missing link updates.

Practice

1. What does the recursive function to reverse a singly linked list primarily do at each step?

easy

A. It iterates through the list using a loop to reverse pointers.

B. It swaps the values of the first and last nodes only.

C. It reverses the rest of the list and then adjusts the current node's next pointer.

D. It creates a new list and copies nodes in reverse order.

Solution

1. Step 1: Understand recursion on linked list

   The function calls itself on the next node until it reaches the end (base case).

2. Step 2: Reverse pointers on return

   After reaching the end, it reverses the next pointer of the current node to point backward.

3. Final Answer:

   It reverses the rest of the list and then adjusts the current node's next pointer. -> Option C

4. Quick Check:

   Recursive reversal = reverse rest + fix pointers [OK]

Hint: Think: reverse rest first, then fix current pointer [OK]

Common Mistakes:

• Trying to swap node values instead of pointers
• Using loops instead of recursion
• Not handling the base case properly

2. Which of the following is the correct base case for a recursive function reversing a singly linked list?

easy

A. if head.next is None: return None

B. if head.next is None: return head.next

C. if head is None: return head.next

D. if head is None or head.next is None: return head

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when the list is empty or has one node.

2. Step 2: Check correct condition

   When head is None (empty) or head.next is None (single node), return head as reversed list.

3. Final Answer:

   if head is None or head.next is None: return head -> Option D

4. Quick Check:

   Base case = empty or single node [OK]

Hint: Base case: empty or single node returns itself [OK]

Common Mistakes:

• Returning None incorrectly for single node
• Missing the empty list check
• Returning head.next instead of head

3. What will be the output linked list after reversing recursively the list: 1 -> 2 -> 3 -> None?

medium

A. 1 -> 2 -> 3 -> None

B. 3 -> 2 -> 1 -> None

C. 2 -> 3 -> 1 -> None

D. None -> 3 -> 2 -> 1

Solution

1. Step 1: Trace recursive calls

   Function calls itself on 2 -> 3 -> None, then on 3 -> None (base case).

2. Step 2: Reverse pointers on return

   On return, 3 points to 2, 2 points to 1, and 1 points to None.

3. Final Answer:

   3 -> 2 -> 1 -> None -> Option B

4. Quick Check:

   Reversed list = 3 -> 2 -> 1 [OK]

Hint: Last node becomes new head after recursion [OK]

Common Mistakes:

• Not updating the last node's next pointer
• Returning original head instead of new head
• Confusing node values with pointers

4. Given this recursive reverse function, what is the error?

def reverse(head):
    if head is None:
        return None
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

medium

A. Base case misses single node check causing AttributeError

B. head.next.next = head causes infinite loop

C. head.next = None should be before recursive call

D. Function returns None always

Solution

1. Step 1: Analyze base case

   Base case only checks if head is None, but not if head.next is None (single node).

2. Step 2: Identify error cause

   When head.next is None, head.next.next causes AttributeError because head.next is None.

3. Final Answer:

   Base case misses single node check causing AttributeError -> Option A

4. Quick Check:

   Missing single node base case = error [OK]

Hint: Always check head.next is None in base case [OK]

Common Mistakes:

• Ignoring single node base case
• Changing pointers before recursion
• Returning None instead of new head

5. How would you modify the recursive reverse function to also return the tail node of the reversed list efficiently?

hard

A. Return a tuple (new_head, tail) and update tail during recursion

B. Use a global variable to track tail node

C. Traverse the reversed list again to find tail after recursion

D. Return only new_head and ignore tail

Solution

1. Step 1: Understand tail tracking need

   To get tail efficiently, return it along with new head during recursion.

2. Step 2: Modify function to return tuple

   Return (new_head, tail) from recursive calls and update tail as current node.

3. Step 3: Avoid extra traversal

   This avoids traversing reversed list again, improving efficiency.

4. Final Answer:

   Return a tuple (new_head, tail) and update tail during recursion -> Option A

5. Quick Check:

   Return (head, tail) tuple for efficiency [OK]

Hint: Return both head and tail as tuple in recursion [OK]

Common Mistakes:

• Using global variables causing side effects
• Traversing list again after reversal
• Ignoring tail node requirement