Reverse a Singly Linked List Recursive in DSA Javascript

Mental Model

We flip the direction of each link in the list by going to the end first, then reversing links on the way back.

Analogy: Imagine unstacking a pile of plates one by one to the bottom, then stacking them back up in reverse order.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Reverse the list so it becomes 3 -> 2 -> 1 -> null

Step 1: call reverse on node 1, recurse to node 2

head -> 1 -> 2 -> 3 -> null ↑ at 1

Why: We need to reach the end before reversing links

Step 2: call reverse on node 2, recurse to node 3

head -> 1 -> 2 -> 3 -> null ↑ at 2

Why: Keep going deeper to the last node

Step 3: call reverse on node 3, base case reached (next is null), return node 3

head -> 1 -> 2 -> 3 -> null ↑ at 3

Why: Last node becomes new head of reversed list

Step 4: reverse link: node 3's next points to node 2, node 2's next set to null

head -> 1 -> 2 ← 3 null ↑ at 2

Why: Flip the link between node 2 and 3

Step 5: reverse link: node 2's next points to node 1, node 1's next set to null

head -> 1 ← 2 ← 3 null ↑ at 1

Why: Flip the link between node 1 and 2

Step 6: return new head node 3, list fully reversed

head -> 3 -> 2 -> 1 -> null

Why: Reversed list ready with new head

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA Javascript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseListRecursive(head) {
  if (head === null || head.next === null) {
    return head; // base case: empty or single node
  }
  const newHead = reverseListRecursive(head.next); // recurse to end
  head.next.next = head; // reverse link: next node points back to current
  head.next = null; // cut old forward link
  return newHead; // return new head up the call stack
}

// Driver code
const node3 = new ListNode(3);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);

const reversedHead = reverseListRecursive(node1);

// Print list function
function printList(head) {
  let curr = head;
  let result = '';
  while (curr !== null) {
    result += curr.val + ' -> ';
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
}

printList(reversedHead);

if (head === null || head.next === null) {

base case: stop recursion at empty or last node

const newHead = reverseListRecursive(head.next);

recurse deeper to reach end of list

head.next.next = head;

reverse link: next node points back to current node

head.next = null;

cut old forward link to avoid cycle

return newHead;

return new head of reversed list up the call stack

Output

3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once during recursion

Space: O(n) due to recursion call stack for n nodes

vs Alternative: Iterative reversal uses O(1) space but recursive is simpler to write and understand

Edge Cases

empty list (head is null)

returns null immediately without recursion

DSA Javascript

if (head === null || head.next === null) {

single node list

returns the single node as is, no reversal needed

DSA Javascript

if (head === null || head.next === null) {

When to Use This Pattern

When you see a problem asking to reverse a linked list and recursion is allowed, use the recursive reversal pattern to flip links from the end back to the start.

Common Mistakes

Mistake: Not setting head.next to null after reversing link, causing a cycle
Fix: Always set head.next = null after reversing the link to break old forward connection

Mistake: Returning head instead of newHead, losing the reversed list head
Fix: Return newHead from recursive calls to keep track of new list head

Summary

Reverses a singly linked list by recursively flipping links from the end to the start.

Use when you want a clean, elegant recursive solution to reverse a linked list.

The key insight is to reverse the link of the next node back to current and cut the old forward link.

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