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

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 recursion goes to the last node, then reverses links on the way back, setting each node's next to previous.

Execution Sample

DSA C#

Node Reverse(Node head) {
  if (head == null || head.next == null) 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 and fixing links.

Execution Table

Step	Operation	Current Node	Recursive Call	Pointer Changes	Visual State
1	Call Reverse on head (1)	1	Reverse(2)	None yet	1 -> 2 -> 3 -> 4 -> null
2	Call Reverse on node 2	2	Reverse(3)	None yet	1 -> 2 -> 3 -> 4 -> null
3	Call Reverse on node 3	3	Reverse(4)	None yet	1 -> 2 -> 3 -> 4 -> null
4	Call Reverse on node 4	4	Base case reached	None yet	1 -> 2 -> 3 -> 4 -> null
5	Return node 4 as new head	4	None	None	1 -> 2 -> 3 -> 4 -> null
6	Reverse link: 4.next = 3	3	None	head.next.next (4.next.next) -> head (3)	1 -> 2 -> 3 <- 4 (4.next = 3)
7	Set 3.next = null	3	None	3.next = null	1 -> 2 -> 3 (null) <- 4
8	Return new head (4)	3	None	None	1 -> 2 -> 3 (null) <- 4
9	Reverse link: 3.next = 2	2	None	head.next.next (3.next.next) -> head (2)	1 -> 2 <- 3 <- 4
10	Set 2.next = null	2	None	2.next = null	1 -> 2 (null) <- 3 <- 4
11	Return new head (4)	2	None	None	1 -> 2 (null) <- 3 <- 4
12	Reverse link: 2.next = 1	1	None	head.next.next (2.next.next) -> head (1)	1 <- 2 <- 3 <- 4
13	Set 1.next = null	1	None	1.next = null	1 (null) <- 2 <- 3 <- 4
14	Return new head (4)	1	None	None	1 (null) <- 2 <- 3 <- 4
15	Final reversed list head is 4	4	None	None	4 -> 3 -> 2 -> 1 -> null

💡 Recursion stops when node is null or last node (step 4), then returns new head back up.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	After Step 13	Final
head	1	4	3	2	1	1 (next=null)
newHead	null	4	4	4	4	4
head.next	2	null	null	null	null	null

Key Moments - 3 Insights

Why do we set head.next = null after reversing the link?

Because after reversing, the original next node points back to current, so current's next must be null to avoid cycles. See steps 7, 10, 13 in execution_table.

Why does recursion stop at the last node?

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

How does the list visually change during recursion return?

Links reverse one by one from the end back to start, changing arrows direction as shown in Visual State column from step 6 onwards.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what pointer change happens?

A head is set to null

B head.next is set to null

C head.next.next points to head

D No pointer changes

💡 Hint

Check the Pointer Changes column at step 6 in execution_table.

At which step does the recursion reach the base case?

A Step 1

B Step 4

C Step 7

D Step 15

💡 Hint

Look for 'Base case reached' in Recursive Call column in execution_table.

If we forget to set head.next = null, what happens to the list?

A List forms a cycle (loop)

B List remains unchanged

C List becomes empty

D List reverses twice

💡 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
- Recursively reverse rest of list
- Set next node's next pointer to current node
- Set current node's next to null
- Return new head from recursion

Full Transcript

This visualization shows how to reverse a singly linked list using recursion. The recursion goes down to the last node, which becomes the new head. Then on the way back, each node's next pointer is reversed to point to the previous node, and the current node's next is set to null to avoid cycles. The execution table tracks each recursive call, pointer changes, and the visual state of the list. Key moments clarify why setting next to null is important and how the base case stops recursion. The quiz tests understanding of pointer changes and recursion steps.

Practice

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

easy

A. Create a new list and copy nodes in reverse order

B. Swap the values of the first and last nodes only

C. Iterate through the list and reverse pointers in a loop

D. Reverse the rest of the list first, then fix the current node's next pointer

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 points back to it, reversing the link.

3. Final Answer:

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

4. Quick Check:

   Recursive reversal = reverse rest then fix current [OK]

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

Common Mistakes:

• Trying to swap node values instead of pointers
• Not fixing the current node's next pointer after recursion
• Using iteration instead of recursion

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 new Node();

B. if (head.next == null) return null;

C. if (head == null || head.next == null) return head;

D. if (head == null) return head.next;

Solution

1. Step 1: Identify when recursion should stop

   The base case is when the list is empty or has only one node, so no reversal needed.

2. Step 2: Check the correct base case syntax

   Return the head itself if it is null or the last node (head.next == null).

3. Final Answer:

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

4. Quick Check:

   Base case = empty or single node returns head [OK]

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

Common Mistakes:

• Returning null when list has one node
• Accessing head.next without checking if head is null
• Creating new nodes unnecessarily

3. What will be the output linked list after running this recursive reverse function on the list 1 -> 2 -> 3 -> null?

Node Reverse(Node head) {
  if (head == null || head.next == null) return head;
  Node newHead = Reverse(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 2 -> 3 -> 1 -> null

D. 3 -> 1 -> 2 -> 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: Fix pointers on return

   head.next.next = head reverses link: 3.next = 2, then 2.next = 1, and 1.next = null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

   Recursive reversal output = reversed list [OK]

Hint: Follow recursion bottom-up to see pointer reversal [OK]

Common Mistakes:

• Not setting head.next to null causing cycle
• Confusing node values with pointers
• Returning wrong node as new head

4. Identify the error in this recursive reverse function and choose the fix:

Node Reverse(Node head) {
  if (head == null) return null;
  Node newHead = Reverse(head.next);
  head.next.next = head;
  return newHead;
}

medium

A. Should return head instead of newHead

B. Missing base case for single node; add 'head.next == null' check

C. head.next.next = head causes null pointer; fix by checking head.next

D. No error; code is correct

Solution

1. Step 1: Check base case correctness

   Base case only checks head == null, missing single node case (head.next == null).

2. Step 2: Consequence of missing base case

   Without single node base case, head.next may be null causing head.next.next to throw error.

3. Final Answer:

   Missing base case for single node; add 'head.next == null' check -> Option B

4. Quick Check:

   Base case must handle empty and single node [OK]

Hint: Base case must cover empty and single node to avoid errors [OK]

Common Mistakes:

• Ignoring single node base case
• Not setting head.next = null after reversal
• Returning wrong node as new head

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 == null || head.next == null) return head;
  Node newHead = Reverse(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

// After reversal, print list from newHead

hard

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

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

C. 40 -> 10 -> 20 -> 30 -> null

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

Solution

1. Step 1: Trace recursive reversal on given list

   Recursion reverses from last node 40 back to 10, fixing pointers step-by-step.

2. Step 2: Confirm final reversed list order

   After reversal, list order is 40 -> 30 -> 20 -> 10 -> null.

3. Final Answer:

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

4. Quick Check:

   Recursive reversal reverses entire list order [OK]

Hint: Reversal flips list order completely [OK]

Common Mistakes:

• Printing original list instead of reversed
• Forgetting to set head.next = null causing cycle
• Misreading pointer changes as value swaps