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

Recall & Review

beginner

What is the base case in the recursive approach to reverse a singly linked list?

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

intermediate

In recursive reversal of a singly linked list, what happens after the recursive call returns?

After the recursive call returns, the next node's next pointer is set to the current node, effectively reversing the link between them. 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 after reversing the link in recursion?

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

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.

beginner

Show the recursive function signature to reverse a singly linked list in C++.

Node* reverseListRecursive(Node* head); // Returns new head of reversed list

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

A The original head of the list

B Null

C The last node visited before recursion

D The new head of the reversed list

The recursive function returns the new head of the reversed list after all recursive calls complete.

Which pointer is changed to reverse the link between two nodes in recursion?

A Current node's next pointer

B Next node's next pointer

C Head pointer

D Previous node's next pointer

The next node's next pointer is set to the current node to reverse the link.

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

A When current node is null or next node is null

B When current node is the head

C When list has more than two nodes

D When current node's next pointer points to head

The recursion stops when the current node is null or the next node is null.

What happens to the current node's next pointer after reversing the link in recursion?

A It remains unchanged

B It points to the previous node

C It is set to null

D It points to the head

It is set to null to avoid cycles and mark the end of the reversed list.

What is the time complexity of recursive reversal of a singly linked list?

A O(n)

B O(n^2)

C O(log n)

D O(1)

Each node is visited once, so the time complexity is linear, O(n).

Explain step-by-step how recursion reverses a singly linked list.

Think about what happens after the recursive call returns.

Write the recursive function to reverse a singly linked list and explain how it works.

Focus on how pointers are changed after recursion.

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 data 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 elements 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's pointer after recursion

   After reversing the rest, the current node's next node should point back to current node, then current node points to null.

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 first [OK]

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

Common Mistakes:

• Trying to swap data instead of pointers
• Not setting current node's next to null
• Confusing iterative and recursive methods

2. Which of the following is the correct base case for a recursive function that reverses a singly linked list?

easy

A. if (head->next == nullptr) return head;

B. if (head == nullptr || head->next == nullptr) return head;

C. if (head == nullptr) return nullptr;

D. if (head->next == nullptr) head = nullptr;

Solution

1. Step 1: Identify base cases for recursion

   Base case should handle empty list and single node list, both are already reversed.

2. Step 2: Choose condition covering both cases

   Condition 'head == nullptr || head->next == nullptr' returns head for empty or single node list.

3. Final Answer:

   if (head == nullptr || head->next == nullptr) return head; -> Option B

4. Quick Check:

   Base case = empty or single node [OK]

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

Common Mistakes:

• Returning nullptr for single node list
• Not handling empty list
• Incorrectly modifying head in base case

3. Given the following linked list: 1 -> 2 -> 3 -> null, what will be the printed output after applying this recursive reverse function?

Node* reverse(Node* head) {
  if (!head || !head->next) return head;
  Node* newHead = reverse(head->next);
  head->next->next = head;
  head->next = nullptr;
  return newHead;
}

medium

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

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

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

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

   On unwind from reverse(3), in reverse(2): head(2)->next(3)->next = 2 so 3->next=2, then 2->next=nullptr. Then in reverse(1): 2->next=1, 1->next=nullptr.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option D

4. Quick Check:

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

Hint: Follow recursion unwind to see pointer reversal [OK]

Common Mistakes:

• Not setting head->next to nullptr causing cycle
• Confusing node values order
• Returning wrong node as new head

4. Identify the bug in this recursive reverse function and select the correct fix:

Node* reverse(Node* head) {
  if (!head || !head->next) return head;
  Node* newHead = reverse(head->next);
  head->next->next = head;
  return newHead;
}

medium

A. Remove the recursive call and use iteration

B. Change base case to 'if (head->next == nullptr) return head;'

C. Add 'head->next = nullptr;' before returning newHead

D. Return 'head' instead of 'newHead'

Solution

1. Step 1: Analyze missing pointer update

   Function misses setting 'head->next = nullptr', causing cycle in reversed list.

2. Step 2: Fix by setting 'head->next = nullptr'

   Adding 'head->next = nullptr;' breaks old link, preventing cycle and correctly terminates list.

3. Final Answer:

   Add 'head->next = nullptr;' before returning newHead -> Option C

4. Quick Check:

   Break old next link to avoid cycle [OK]

Hint: Always set current node's next to nullptr after reversing [OK]

Common Mistakes:

• Forgetting to break old next pointer
• Incorrect base case causing null pointer dereference
• Returning wrong node as new head

5. You want to reverse a singly linked list recursively but also count how many nodes were reversed. Which modification correctly adds counting without breaking the reversal?

Node* reverseCount(Node* head, int &count) {
  if (!head || !head->next) {
    count++;
    return head;
  }
  Node* newHead = reverseCount(head->next, count);
  head->next->next = head;
  head->next = nullptr;
  count++;
  return newHead;
}

What will be the value of count after reversing a list with 4 nodes?

hard

A. 4

B. 3

C. 5

D. 0

Solution

1. Step 1: Understand counting in base case

   When recursion reaches last node, count increments by 1 for that node.

2. Step 2: Count increments on each return step

   Each return from recursion increments count by 1 for each node processed, total nodes counted equals list length.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count increments once per node [OK]

Hint: Increment count once per node during recursion [OK]

Common Mistakes:

• Counting only in base case missing other nodes
• Incrementing count twice per node
• Not passing count by reference