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.