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

Concept Flow - Reverse a Singly Linked List Recursive

Start with head node

↓

Check if node is NULL or last node

Yes↓

Return node as new head

No↓

Recursive call on next node

↓

Reverse link: next->next = current

↓

Set current->next = NULL

↓

Return new head from recursion

The function recursively goes to the last node, then reverses the links on the way back, setting each node's next pointer to its previous node.

Execution Sample

DSA C

Node* reverse(Node* head) {
  if (!head || !head->next) return head;
  Node* newHead = reverse(head->next);
  head->next->next = head;
  head->next = NULL;
  return newHead;
}

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

Execution Table

Step	Operation	Current Node	Recursive Call Result	Pointer Changes	Visual State
1	Call reverse(head=1)	1	Calls reverse(2)	None yet	1 -> 2 -> 3 -> NULL
2	Call reverse(head=2)	2	Calls reverse(3)	None yet	1 -> 2 -> 3 -> NULL
3	Call reverse(head=3)	3	Base case reached, returns 3	None yet	1 -> 2 -> 3 -> NULL
4	Reverse link at node 2	2	newHead=3	3->next = 2, 2->next = NULL	1 -> 2(NULL) <- 3
5	Reverse link at node 1	1	newHead=3	2->next = 1, 1->next = NULL	1(NULL) <- 2 <- 3
6	Return newHead=3	NULL	3	No change	3 -> 2 -> 1 -> NULL

💡 Recursion ends when head is last node (3), then links reversed on return

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	1	1	2	3	2	1	NULL
newHead	NULL	NULL	NULL	3	3	3	3
List Visual	1->2->3->NULL	1->2->3->NULL	1->2->3->NULL	1->2->3->NULL	1->2(NULL)<-3	1(NULL)<-2<-3	3->2->1->NULL

Key Moments - 3 Insights

Why do we set head->next = NULL after reversing the link?

Because after reversing, the current node becomes the last node in the reversed part, so its next must point to NULL to avoid cycles. See step 4 and 5 in execution_table.

Why does the recursion stop at the last node (head->next == NULL)?

Because the last node is the new head of the reversed list. The base case returns this node without further recursion, as shown in step 3.

How does the recursive call return the new head to all previous calls?

Each recursive call returns the new head from the deepest call (last node). This is stored in newHead and passed back up, as seen in steps 4 and 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after step 4?

A 1 -> 2 -> 3 -> NULL

B 1 -> 2(NULL) <- 3

C 1(NULL) <- 2 <- 3

D 3 -> 2 -> 1 -> NULL

💡 Hint

Check the 'Visual State' column at step 4 in execution_table.

At which step does the recursion reach the base case?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for the step where the function returns without further recursive calls in execution_table.

If we forget to set head->next = NULL, what would happen to the list?

A The list would be correctly reversed

B The list would become empty

C The list would have a cycle causing infinite loop

D The list would remain unchanged

💡 Hint

Refer to key_moments about why head->next is set to NULL after reversing links.

Concept Snapshot

Reverse a singly linked list recursively:
- Base case: if node is NULL or last, return node
- Recursive call on next node
- Reverse link: next->next = current
- Set current->next = NULL
- Return new head from recursion

Full Transcript

This concept 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's next pointer back to the current node and setting the current node's next pointer to NULL. This process continues until all nodes are reversed. The execution table traces each step, showing the current node, recursive calls, pointer changes, and the visual state of the list. Key moments clarify why we set the next pointer to NULL and how recursion returns the new head. The visual quiz tests understanding of these steps.