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

Concept Flow - Reverse a Singly Linked List Recursive

Start with head node

↓

Base case: head == null or head.next == null?

|Yes↓

Return head as new head

No↓

Recursive call: reverse(head.next)

↓

Reverse link: head.next.next = head

↓

Set head.next = null

↓

Return new head from recursion

↓

Done

The recursion goes to the last node, then reverses links on the way back, setting each next node's next pointer back to current node.

Execution Sample

DSA Java

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 of the list and then fixing the current node's next pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Call reverse on head (1)	1 -> 2 -> 3 -> null	No change	1 -> 2 -> 3 -> null
2	Call reverse on head.next (2)	1 -> 2 -> 3 -> null	No change	1 -> 2 -> 3 -> null
3	Call reverse on head.next.next (3)	1 -> 2 -> 3 -> null	No change	1 -> 2 -> 3 -> null
4	Base case reached at node 3 (head.next == null), return node 3	1 -> 2 -> 3 -> null	No change	1 -> 2 -> 3 -> null
5	Reverse link: node 2.next.next = node 2	1 -> 2 -> 3 -> null	3.next = 2	1 -> 2 <- 3 (3.next points to 2)
6	Set node 2.next = null	1 -> 2 -> 3 -> null	2.next = null	1 -> 2 null 3 -> 2
7	Return new head (node 3) to previous call	1 -> 2 null 3 -> 2	No change	1 -> 2 null 3 -> 2
8	Reverse link: node 1.next.next = node 1	1 -> 2 null 3 -> 2	2.next = 1	1 <- 2 <- 3
9	Set node 1.next = null	1 -> 2 null 3 -> 2	1.next = null	1 null 2 -> 1 3 -> 2
10	Return new head (node 3) as final reversed list head	1 null 2 -> 1 3 -> 2	No change	3 -> 2 -> 1 -> null

💡 Recursion ends when head.next is null (node 3), then links are reversed on return.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 9	Final
head	1	3	2	1	1
head.next	2	null	null	null	null
newHead	null	3	3	3	3
List Visual	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> null	1 -> 2 null 3 -> 2	1 null 2 -> 1 3 -> 2	3 -> 2 -> 1 -> 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 head, so to avoid a cycle, we must set head.next to null. See step 6 and 9 in execution_table.

Why does the recursion stop at head.next == null?

Because the last node has no next node, it becomes the new head of the reversed list. This is the base case at step 4.

How does the list visually change after step 5?

At step 5, the next node's next pointer points back to current node, reversing the link between nodes 2 and 3, shown as 1 -> 2 <- 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the state of node 2's next pointer?

A node 2.next is null

B node 2.next points to node 1

C node 2.next points to node 3

D node 2.next points to itself

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6 in execution_table.

At which step does the recursion reach the base case?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step mentioning 'Base case reached' in execution_table.

If we did not 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 explanation about setting head.next = null to avoid cycles.

Concept Snapshot

Reverse a singly linked list recursively:
- Base case: if head is null or head.next is null, return head
- Recursively reverse rest of list
- Set head.next.next = head to reverse link
- Set head.next = null to avoid cycle
- 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 making the next node point back to the current node and setting the current node's next pointer to null to avoid cycles. The execution table tracks each step, showing pointer changes and the visual state of the list. Key moments clarify why setting head.next to null is necessary and why recursion stops at the last node. The quiz tests understanding of pointer changes and recursion base case.

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 values 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 nodes 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 after recursive call

   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 A

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
• Reversing pointers before recursive call
• 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 null.next;

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

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

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

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when list is empty or has one node, so head is null or head.next is null.

2. Step 2: Check each option

   if (head == null || head.next == null) return head; correctly returns head when list is empty or single node. Others cause errors or wrong returns.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Returning null when list has one node
• Accessing next of null causing errors
• Missing base case leading to infinite recursion

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. null

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

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

D. 3 -> 1 -> 2 -> null

Solution

1. Step 1: Trace recursion on list 1->2->3

   Recursion goes to last node 3, then reverses links backward: 3 points to 2, 2 points to 1.

2. Step 2: Final reversed list

   After fixing pointers, the list becomes 3 -> 2 -> 1 -> null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Not setting head.next to null causing cycle
• Returning old head instead of new head
• Confusing node values with pointers

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. head.next.next = head; should be head.next = head.next.next;

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

C. Return statement should be 'return head;' instead of newHead

D. No error; code is correct

Solution

1. Step 1: Check base case correctness

   Base case only checks head == null, missing single node case causes null pointer error at head.next.next.

2. Step 2: Fix base case

   Adding 'head.next == null' to base case prevents error and correctly stops recursion.

3. Final Answer:

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

4. Quick Check:

   Base case must handle single node [OK]

Hint: Base case must check single node to avoid null pointer [OK]

Common Mistakes:

• Ignoring single node base case causing runtime error
• Incorrect pointer assignment causing infinite loop
• Returning wrong node after recursion

5. Given a singly linked list with nodes 10 -> 20 -> 30 -> 40 -> null, you want to reverse it recursively but also count how many nodes were reversed. Which modification correctly adds counting nodes during recursion?

class Result {
  Node head;
  int count;
}

Result reverseCount(Node head) {
  if (head == null || head.next == null) {
    Result res = new Result();
    res.head = head;
    res.count = (head == null) ? 0 : 1;
    return res;
  }
  Result res = reverseCount(head.next);
  head.next.next = head;
  head.next = null;
  res.count += 1;
  return res;
}

hard

A. This code correctly reverses and counts nodes

B. Count should be incremented before recursive call

C. head.next = null; should be removed to avoid breaking list

D. Result class should store count as static variable

Solution

1. Step 1: Analyze recursive counting logic

   Base case sets count to 1 or 0. Each recursive return increments count by 1 after reversing pointer.

2. Step 2: Confirm correctness of pointer reversal and counting

   Pointer reversal is correct and count increments after recursion, so total nodes counted correctly.

3. Final Answer:

   This code correctly reverses and counts nodes -> Option A

4. Quick Check:

   Counting nodes during recursion works as coded [OK]

Hint: Increment count after recursion to count all nodes [OK]

Common Mistakes:

• Incrementing count before recursion causing wrong totals
• Removing head.next = null causing cycles
• Using static variable causing shared state bugs