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.

Practice

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

easy

A. Use a stack to store nodes and pop them in reverse order

B. Reverse the rest of the list and then fix the first node's next pointer

C. Swap the data values of nodes from start to end

D. Iterate through the list and reverse pointers one by one

Solution

1. Step 1: Understand recursion on linked list

   Recursion reverses the list from the second node onward first.

2. Step 2: Fix the first node's next pointer

   After recursion returns, the first node's next pointer is set to null and the previous node points back to it.

3. Final Answer:

   Reverse the rest of the list and then fix the first node's next pointer -> Option B

4. Quick Check:

   Recursive reversal = Reverse rest + fix first [OK]

Hint: Think: reverse smaller list first, then fix current node [OK]

Common Mistakes:

• Trying to swap node data instead of pointers
• Not setting the first node's next to null
• Confusing iterative and recursive methods

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

easy

A. if (head == NULL) return NULL;

B. if (head->next == NULL) return head;

C. if (head == NULL || head->next == NULL) return head;

D. if (head->next == NULL) head = NULL;

Solution

1. Step 1: Identify base cases for recursion

   Base case must handle empty list and single node list to stop recursion.

2. Step 2: Choose correct condition

   Condition 'head == NULL || head->next == NULL' covers both empty and single node cases.

3. Final Answer:

   if (head == NULL || head->next == NULL) return head; -> Option C

4. Quick Check:

   Base case = empty or single node [OK]

Hint: Base case stops recursion on empty or single node [OK]

Common Mistakes:

• Returning NULL for single node list
• Not handling empty list as base case
• Incorrectly modifying head in base case

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

medium

A. 3 -> 1 -> 2 -> NULL

B. 1 -> 2 -> 3 -> NULL

C. 2 -> 3 -> 1 -> NULL

D. 3 -> 2 -> 1 -> NULL

Solution

1. Step 1: Trace recursive reversal

   Recursion reverses from last node back: 3 becomes new head, 2 points to 1, 1 points to NULL.

2. Step 2: Confirm final list order

   Final reversed list is 3 -> 2 -> 1 -> NULL.

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option D

4. Quick Check:

   Reverse(1->2->3) = 3->2->1 [OK]

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

Common Mistakes:

• Assuming original order remains
• Mixing node values instead of pointers
• Forgetting to set last node's next to NULL

4. Identify the error in this recursive reverse function snippet:

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

medium

A. head->next is set to head instead of NULL causing a cycle

B. Missing base case for empty list

C. Incorrect return value; should return head

D. No recursive call made

Solution

1. Step 1: Analyze pointer assignments

   head->next->next = head correctly points next node back to current node.

2. Step 2: Identify incorrect pointer reset

   head->next = head wrongly points current node's next to itself, causing a cycle instead of NULL.

3. Final Answer:

   head->next is set to head instead of NULL causing a cycle -> Option A

4. Quick Check:

   head->next must be NULL, not head [OK]

Hint: Set head->next to NULL to avoid cycles [OK]

Common Mistakes:

• Setting head->next to head causing infinite loop
• Forgetting to return the new head
• Not handling base case properly

5. Given a singly linked list with nodes containing values 10 -> 20 -> 30 -> 40 -> NULL, what will be the printed output after applying this recursive reverse function?

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

void printList(Node* head) {
  while (head) {
    printf("%d -> ", head->data);
    head = head->next;
  }
  printf("NULL\n");
}

int main() {
  // List creation omitted for brevity
  Node* reversed = reverse(head);
  printList(reversed);
}

hard

A. 40 -> 30 -> 20 -> 10 -> NULL

B. 10 -> 20 -> 30 -> 40 -> NULL

C. NULL

D. 40 -> 20 -> 30 -> 10 -> NULL

Solution

1. Step 1: Trace recursive reversal on list 10->20->30->40

   Recursion reverses from last node: 40 becomes new head, pointers reversed stepwise.

2. Step 2: Confirm print output

   Print function outputs nodes in order: 40 -> 30 -> 20 -> 10 -> NULL.

3. Final Answer:

   40 -> 30 -> 20 -> 10 -> NULL -> Option A

4. Quick Check:

   Reverse(10->20->30->40) = 40->30->20->10 [OK]

Hint: Last node becomes head; print from new head [OK]

Common Mistakes:

• Assuming original order remains after reverse
• Forgetting to set last node's next to NULL
• Confusing print output with input list