Reverse a Singly Linked List Recursive in DSA C++

Mental Model

We flip the direction of the list by reversing the rest first, then fixing the current node's pointer.

Analogy: Imagine flipping a row of dominoes one by one from the end back to the start, turning each domino to face the opposite way after the next is flipped.

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

Dry Run Walkthrough

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

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

Step 1: call reverse on node 1; move to next node 2

1 -> [2 -> 3 -> null]

Why: We need to reverse the rest of the list before fixing node 1

Step 2: call reverse on node 2; move to next node 3

2 -> [3 -> null]

Why: Keep going until we reach the last node

Step 3: call reverse on node 3; base case reached, return node 3

3 -> null

Why: Last node becomes new head of reversed list

Step 4: fix node 3's next pointer to point back to node 2

3 -> 2 -> null

Why: Reverse the link between node 2 and node 3

Step 5: fix node 2's next pointer to point back to node 1

3 -> 2 -> 1 -> null

Why: Reverse the link between node 1 and node 2

Step 6: set node 1's next pointer to null to end the list

3 -> 2 -> 1 -> null

Why: Old head now becomes tail, so next must be null

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

Node* reverseRecursive(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head; // base case: empty or single node
    }
    Node* newHead = reverseRecursive(head->next); // reverse rest
    head->next->next = head; // fix next node's next pointer to current
    head->next = nullptr; // current becomes tail
    return newHead; // new head of reversed list
}

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << " -> null" << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    cout << "Original list: ";
    printList(head);

    head = reverseRecursive(head);

    cout << "Reversed list: ";
    printList(head);

    return 0;
}

if (head == nullptr || head->next == nullptr) {

base case: stop recursion at empty or single node

Node* newHead = reverseRecursive(head->next);

recursively reverse the rest of the list

head->next->next = head;

reverse the pointer of the next node to point back to current

head->next = nullptr;

set current node's next to null to mark new tail

return newHead;

return new head of reversed list up the call stack

Output

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

Reversed list: 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 recursion is simpler to write and understand

Edge Cases

empty list (head is nullptr)

function returns nullptr immediately without error

DSA C++

if (head == nullptr || head->next == nullptr) {

single node list

function returns the single node as is, no changes

DSA C++

if (head == nullptr || head->next == nullptr) {

When to Use This Pattern

When you need to reverse a linked list and want a clean, elegant solution, use recursion to reverse the rest first, then fix the current node's pointer.

Common Mistakes

Mistake: Not setting the current node's next pointer to null, causing cycles
Fix: Set head->next = nullptr after reversing the next node's pointer

Mistake: Returning head instead of newHead, losing the new list head
Fix: Return the newHead returned by the recursive call

Summary

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

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

The key is to reverse the rest first, then fix the current node's pointer to point backward.

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