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 head is NULL or head->next is NULL?

Yes→Return head (base case)

No↓

Recursive call: reverse(head->next)

↓

After recursion returns: head->next->next = head

↓

Set head->next = NULL

↓

Return new head from recursion

↓

Done: List reversed

The function recursively reverses the list by going to the end, then rewiring pointers backward step-by-step.

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 recursively by rewiring pointers from the end back to the start.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Call reverse with head=1	1->2->3->4->NULL	No change	1 -> 2 -> 3 -> 4 -> NULL
2	Call reverse with head=2	1->2->3->4->NULL	No change	1 -> 2 -> 3 -> 4 -> NULL
3	Call reverse with head=3	1->2->3->4->NULL	No change	1 -> 2 -> 3 -> 4 -> NULL
4	Call reverse with head=4	1->2->3->4->NULL	No change	1 -> 2 -> 3 -> 4 -> NULL
5	Base case reached (head=4)	4->NULL	Return head=4	4 -> NULL
6	Rewire: head=3, head->next=4, set 4->next=3	1->2->3->4->NULL	4->next = 3	1 -> 2 -> 3 <- 4 (3->next still 4)
7	Set 3->next = NULL	1->2->3->4->NULL	3->next = NULL	1 -> 2 -> 3(NULL) <- 4
8	Return newHead=4 to previous call	1->2->3->4->NULL	No change	4 -> 3 -> NULL
9	Rewire: head=2, head->next=3, set 3->next=2	1->2->3->4->NULL	3->next = 2	1 -> 2 <- 3 <- 4
10	Set 2->next = NULL	1->2->3->4->NULL	2->next = NULL	1 -> 2(NULL) <- 3 <- 4
11	Return newHead=4 to previous call	1->2->3->4->NULL	No change	4 -> 3 -> 2 -> NULL
12	Rewire: head=1, head->next=2, set 2->next=1	1->2->3->4->NULL	2->next = 1	1 <- 2 <- 3 <- 4
13	Set 1->next = NULL	1->2->3->4->NULL	1->next = NULL	1(NULL) <- 2 <- 3 <- 4
14	Return newHead=4 (final)	1->2->3->4->NULL	No change	4 -> 3 -> 2 -> 1 -> NULL
15	End of recursion, reversed list returned	4->3->2->1->NULL	No change	4 -> 3 -> 2 -> 1 -> NULL

💡 Recursion ends when head is last node (4), then rewiring happens on return steps until full list reversed.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 7	After Step 10	After Step 13	Final
head	1	1	4	3	2	1	1
newHead	undefined	undefined	4	4	4	4	4
head->next	2	2	NULL	NULL	NULL	NULL	NULL

Key Moments - 3 Insights

Why do we set head->next = NULL after rewiring?

Because after setting head->next->next = head, the original next pointer still points forward, causing a cycle. Setting head->next = NULL breaks the old forward link, as shown in steps 7, 10, and 13 in the execution_table.

Why does the recursion stop at the last node?

The base case returns the last node as new head when head->next is NULL (step 5). This stops further recursion and starts rewiring backward.

How does the list visually change during rewiring?

Initially, arrows point forward (1->2->3->4). After rewiring, arrows reverse step-by-step (4->3->2->1), as seen in the Visual State column from steps 6 to 15.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the pointer change made?

A head->next = NULL

B head->next->next = head

C Return newHead

D No pointer change

💡 Hint

Check the Pointer Changes column at step 7 in execution_table.

At which step does the recursion base case occur?

A Step 4

B Step 5

C Step 6

D Step 1

💡 Hint

Look for 'Base case reached' in the Operation column of execution_table.

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

A List becomes empty

B List remains unchanged

C List forms a cycle (loop)

D List reverses correctly

💡 Hint

Refer to key_moments explanation about pointer rewiring and cycles.

Concept Snapshot

Recursive Reverse of Singly Linked List:
- Base case: if head is NULL or head->next is NULL, return head
- Recursively reverse from head->next
- Set head->next->next = head to reverse pointer
- Set head->next = NULL to break old link
- Return new head from recursion
- Result: list reversed step-by-step from end to start

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, as recursion unwinds, it rewires each node's next pointer to point backward, breaking the old forward link by setting head->next to NULL. The execution table traces each recursive call and pointer change, showing the list nodes and their connections visually. Key moments clarify why breaking the old link is necessary to avoid cycles and how the base case stops recursion. The visual quiz tests understanding of pointer changes and recursion steps. This method reverses the list cleanly and elegantly using recursion.

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 fix the current node's next pointer

B. Swap the data 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 recursion on linked list

   Recursion works by solving a smaller part first, here reversing from the next node onward.

2. Step 2: Fix current node's pointer after recursion

   After reversing the rest, the current node's next node should point back to current node, then current node points to null.

3. Final Answer:

   Reverse the rest of the list first, then fix the current node's next pointer -> Option A

4. Quick Check:

   Recursive reversal = Reverse rest first [OK]

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

Common Mistakes:

• Trying to swap data instead of pointers
• Not setting current 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->next == nullptr) return head;

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

C. if (head == nullptr) return nullptr;

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

Solution

1. Step 1: Identify base cases for recursion

   Base case should handle empty list and single node list, both are already reversed.

2. Step 2: Choose condition covering both cases

   Condition 'head == nullptr || head->next == nullptr' returns head for empty or single node list.

3. Final Answer:

   if (head == nullptr || head->next == nullptr) return head; -> Option B

4. Quick Check:

   Base case = empty or single node [OK]

Hint: Base case covers empty or single node list [OK]

Common Mistakes:

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

3. Given the following linked list: 1 -> 2 -> 3 -> null, what will be the printed output after applying this recursive reverse function?

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

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 recursion calls

   reverse(1) calls reverse(2), which calls reverse(3). reverse(3) returns node 3 as base case.

2. Step 2: Reverse pointers on return

   On unwind from reverse(3), in reverse(2): head(2)->next(3)->next = 2 so 3->next=2, then 2->next=nullptr. Then in reverse(1): 2->next=1, 1->next=nullptr.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option D

4. Quick Check:

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

Hint: Follow recursion unwind to see pointer reversal [OK]

Common Mistakes:

• Not setting head->next to nullptr causing cycle
• Confusing node values order
• Returning wrong node as new head

4. Identify the bug in this recursive reverse function and select the correct fix:

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

medium

A. Remove the recursive call and use iteration

B. Change base case to 'if (head->next == nullptr) return head;'

C. Add 'head->next = nullptr;' before returning newHead

D. Return 'head' instead of 'newHead'

Solution

1. Step 1: Analyze missing pointer update

   Function misses setting 'head->next = nullptr', causing cycle in reversed list.

2. Step 2: Fix by setting 'head->next = nullptr'

   Adding 'head->next = nullptr;' breaks old link, preventing cycle and correctly terminates list.

3. Final Answer:

   Add 'head->next = nullptr;' before returning newHead -> Option C

4. Quick Check:

   Break old next link to avoid cycle [OK]

Hint: Always set current node's next to nullptr after reversing [OK]

Common Mistakes:

• Forgetting to break old next pointer
• Incorrect base case causing null pointer dereference
• Returning wrong node as new head

5. You want to reverse a singly linked list recursively but also count how many nodes were reversed. Which modification correctly adds counting without breaking the reversal?

Node* reverseCount(Node* head, int &count) {
  if (!head || !head->next) {
    count++;
    return head;
  }
  Node* newHead = reverseCount(head->next, count);
  head->next->next = head;
  head->next = nullptr;
  count++;
  return newHead;
}

What will be the value of count after reversing a list with 4 nodes?

hard

A. 4

B. 3

C. 5

D. 0

Solution

1. Step 1: Understand counting in base case

   When recursion reaches last node, count increments by 1 for that node.

2. Step 2: Count increments on each return step

   Each return from recursion increments count by 1 for each node processed, total nodes counted equals list length.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count increments once per node [OK]

Hint: Increment count once per node during recursion [OK]

Common Mistakes:

• Counting only in base case missing other nodes
• Incrementing count twice per node
• Not passing count by reference