Reverse a Singly Linked List Recursive in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in the recursive reversal of a singly linked list?

The base case is when the current node is null or its next node is null, meaning we have reached the end or the list is empty. This node becomes the new head of the reversed list.

intermediate

In recursive reversal, what happens after the recursive call returns the new head?

After the recursive call returns the new head, the next node's next pointer is set to the current node, reversing the link. Then, the current node's next pointer is set to null to avoid cycles.

beginner

Why do we set the current node's next pointer to null in recursive reversal?

Setting the current node's next pointer to null breaks the original forward link, preventing cycles and correctly terminating the reversed list at the current node.

beginner

Show the recursive function signature for reversing a singly linked list in Java.

public ListNode reverseList(ListNode head) { ... } where ListNode is the node class with 'int val' and 'ListNode next'.

beginner

What is the time complexity of reversing a singly linked list recursively?

The time complexity is O(n), where n is the number of nodes, because each node is visited exactly once during the recursion.

What does the recursive function return when reversing a singly linked list?

A The original head of the list

B The new head of the reversed list

C The last node visited before recursion

D Null

The recursive function returns the new head of the reversed list after fully reversing the links.

In recursive reversal, what is the role of the statement 'head.next.next = head;'?

A It reverses the link by pointing the next node back to the current node

B It moves the head pointer forward

C It deletes the current node

D It sets the head to null

This statement reverses the link by making the next node point back to the current node.

What happens if you forget to set 'head.next = null;' in recursive reversal?

A The list will be empty

B The list will be reversed correctly

C The list may form a cycle causing infinite loops

D The recursion will stop early

Not setting 'head.next = null;' leaves old forward links intact, causing cycles and potential infinite loops.

Which of these is NOT a characteristic of recursive reversal of a singly linked list?

A Uses stack frames to hold nodes during recursion

B Modifies the list in place without creating new nodes

C Reverses links during the unwinding phase

D Requires extra memory proportional to list size

Recursive reversal uses call stack memory but does not create new nodes, so extra memory is only for recursion stack, not new nodes.

What is the base condition to stop recursion when reversing a singly linked list?

A When head is null or head.next is null

B When head is the first node

C When head.next.next is null

D When head points to itself

Recursion stops when the current node is null or the last node (head.next is null).

Explain step-by-step how recursive reversal of a singly linked list works.

Think about what happens when recursion reaches the end and how links are reversed on the way back.

Write the recursive Java function to reverse a singly linked list and explain each line.

Start with base case, then recursive call, then pointer reversal, and finally return.

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