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

Concept Flow - Reverse a Singly Linked List Recursive

Start with head node

↓

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

|Yes↓

Return head as new head

No↓

Recursive call: reverseList(head.next)

↓

After recursion returns: head.next.next = head

↓

Set head.next = null

↓

Return new head from recursion

↓

Done: list reversed

The function calls itself moving to the end of the list, then reverses links on the way back.

Execution Sample

DSA Javascript

function reverseList(head) {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Recursively reverses a singly linked list by reversing pointers from the end back to the start.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Call reverseList with head=1	1 -> 2 -> 3 -> 4 -> null	None	1 -> 2 -> 3 -> 4 -> null
2	Call reverseList with head=2	1 -> 2 -> 3 -> 4 -> null	None	1 -> 2 -> 3 -> 4 -> null
3	Call reverseList with head=3	1 -> 2 -> 3 -> 4 -> null	None	1 -> 2 -> 3 -> 4 -> null
4	Call reverseList with head=4 (base case)	1 -> 2 -> 3 -> 4 -> null	None	1 -> 2 -> 3 -> 4 -> null
5	Return head=4 as newHead	1 -> 2 -> 3 -> 4 -> null	None	1 -> 2 -> 3 -> 4 -> null
6	head=3: head.next.next = head (4.next = 3)	1 -> 2 -> 3 -> 4 -> null	4.next = 3	1 -> 2 -> 3 <- 4 null
7	head=3: head.next = null (3.next = null)	1 -> 2 -> 3 4 -> 3	3.next = null	1 -> 2 -> 3 4 -> 3 null
8	Return newHead=4	1 -> 2 -> 3 4 -> 3 null	None	1 -> 2 -> 3 4 -> 3 null
9	head=2: head.next.next = head (3.next = 2)	1 -> 2 -> 3 4 -> 3 null	3.next = 2	1 -> 2 3 <- 4 null
10	head=2: head.next = null (2.next = null)	1 -> 2 3 <- 4 null	2.next = null	1 -> 2 3 <- 4 null
11	Return newHead=4	1 -> 2 3 <- 4 null	None	1 -> 2 3 <- 4 null
12	head=1: head.next.next = head (2.next = 1)	1 -> 2 3 <- 4 null	2.next = 1	1 2 <- 3 <- 4 null
13	head=1: head.next = null (1.next = null)	1 2 <- 3 <- 4 null	1.next = null	1 2 <- 3 <- 4 null
14	Return newHead=4 (final reversed list)	1 2 <- 3 <- 4 null	None	4 -> 3 -> 2 -> 1 -> null

💡 Recursion ends when head is last node (4), then pointers reversed on return.

Variable Tracker

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

Key Moments - 3 Insights

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

Because after reversing, the original next node points back to head, so head.next must be null to avoid cycles. See steps 7, 10, and 13 in 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 4). This stops further recursion and starts reversing pointers.

How does the list look during recursion before pointers reverse?

The list remains unchanged during recursive calls (steps 1-4). Only when recursion returns do pointers reverse (steps 6 onward).

Visual Quiz - 3 Questions

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

A 4.next points to 3

B 3.next points to 4

C 3.next is set to null

D 2.next points to 3

💡 Hint

Check 'Pointer Changes' column at step 6 in execution_table.

At which step does head.next get set to null for the first time?

A Step 10

B Step 6

C Step 7

D Step 13

💡 Hint

Look for 'head.next = null' in Pointer Changes column in execution_table.

If the list had only one node, what would the function return immediately?

A null

B the single node itself

C undefined

D an error

💡 Hint

Refer to base case in concept_flow and step 4 in execution_table.

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 avoid cycle
- Return new head from recursion
- Result: list reversed in place

Full Transcript

This visualization shows how a singly linked list is reversed using recursion. The function calls itself moving to the last node, then reverses the pointers on the way back. The base case returns the last node as the new head. Each step reverses the pointer of the next node to point back to the current node and sets the current node's next to null to avoid cycles. The final returned node is the new head of the reversed list.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand recursion on linked list

   Recursion reverses the list by first reversing the smaller list after the current node.

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

   After recursion returns, the current node's next node points back to the current node, reversing the link.

3. Final Answer:

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

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
• Using iteration instead of recursion
• Not fixing the current node's next pointer after 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 head;

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

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

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

Solution

1. Step 1: Identify base cases for recursion

   The base case must handle empty list (null) and single node list (next is null).

2. Step 2: Combine conditions for base case

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

3. Final Answer:

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

4. Quick Check:

   Base case = empty or single node list [OK]

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

Common Mistakes:

• Using only null check without single node check
• Returning wrong node in base case
• Checking head.next.next which may cause error if head.next is null

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

function reverseList(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

medium

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

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

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

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

Solution

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

   Recursion reaches last node 3, returns it as new head.

2. Step 2: Reverse pointers on unwind

   Node 2's next (3) points back to 2, then 2's next set to null; similarly for node 1.

3. Final Answer:

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

4. Quick Check:

   Recursive reversal output = reversed list [OK]

Hint: Last node becomes new head, pointers reversed on return [OK]

Common Mistakes:

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

4. Identify the error in this recursive reverse function:

function reverseList(head) {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next = head;
  head.next = null;
  return newHead;
}

medium

A. head.next = head; creates a cycle, should be head.next.next = head;

B. Base case is missing for empty list

C. Function does not return newHead

D. head.next is set to null before recursion

Solution

1. Step 1: Analyze pointer assignment

   head.next = head sets next pointer of current node to itself, causing cycle.

2. Step 2: Correct pointer fix

   It should be head.next.next = head to reverse the link properly.

3. Final Answer:

   head.next = head; creates a cycle, should be head.next.next = head; -> Option A

4. Quick Check:

   Pointer fix must be head.next.next = head [OK]

Hint: Fix pointer with head.next.next = head, not head.next = head [OK]

Common Mistakes:

• Assigning head.next to head causing infinite loop
• Forgetting to set head.next to null
• Incorrect base case handling

5. Given a singly linked list with nodes containing values [10, 20, 30, 40, 50], how would you modify the recursive reverse function to also count the number of nodes reversed and return it along with the new head?

hard

A. Return an object {newHead, count} from recursion and increment count on unwind

B. Use a global variable to count nodes during recursion

C. Count nodes before recursion and return only new head

D. Modify nodes to store count and update during recursion

Solution

1. Step 1: Change recursion to return both head and count

   Return an object with newHead and count from each recursive call.

2. Step 2: Increment count on each unwind step

   When recursion returns, add 1 to count to track nodes reversed.

3. Final Answer:

   Return an object {newHead, count} from recursion and increment count on unwind -> Option A

4. Quick Check:

   Return combined result object with count [OK]

Hint: Return object with head and count, increment count on return [OK]

Common Mistakes:

• Using global variables causing side effects
• Counting nodes before reversal, not during recursion
• Modifying node structure unnecessarily