Reverse a Singly Linked List Recursive in DSA C++ - Build from Scratch

Reverse a Singly Linked List Recursive

📖 Scenario: Imagine you have a chain of train cars connected one after another. Sometimes, you want to reverse the order of the cars so the last car becomes the first. This is like reversing a singly linked list, where each car is a node pointing to the next.

🎯 Goal: You will build a singly linked list with exact values, then write a recursive function to reverse the list, and finally print the reversed list to see the new order.

📋 What You'll Learn

Create a singly linked list with nodes containing values 10, 20, 30, 40, 50 in that order.

Write a recursive function called reverseList that takes the head node and returns the new head of the reversed list.

Print the reversed list nodes in order separated by ' -> ' and ending with 'null'.

💡 Why This Matters

🌍 Real World

Reversing linked lists is useful in many applications like undo operations, navigation history, and data processing pipelines where order reversal is needed.

💼 Career

Understanding linked list reversal is a common interview question and helps build strong problem-solving skills in data structures.

1

Create the singly linked list

Create a struct called Node with an int data and a Node* next. Then create nodes with values 10, 20, 30, 40, and 50 linked in that order. Finally, create a Node* called head pointing to the first node.

DSA C++

// Define Node struct and create linked list nodes with values 10, 20, 30, 40, 50 linked
// Set head to point to the first node
// Your code here

Hint

Start by defining the Node structure. Then create each node with the given values and link them by setting the next pointers. Finally, set head to the first node.

2

Add the recursive reverse function declaration

Declare a function called reverseList that takes a Node* parameter named head and returns a Node*. This function will reverse the linked list recursively.

DSA C++

struct Node {
    int data;
    Node* next;
};

Node node1 = {10, nullptr};
Node node2 = {20, nullptr};
Node node3 = {30, nullptr};
Node node4 = {40, nullptr};
Node node5 = {50, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;

Node* head = &node1;

// Declare the recursive function reverseList here
// Your code here

Hint

Write the function declaration with the exact name reverseList, taking Node* head and returning Node*.

3

Implement the recursive reverse function

Implement the reverseList function recursively. If head is nullptr or head->next is nullptr, return head. Otherwise, recursively reverse the rest of the list, then set head->next->next = head and head->next = nullptr. Finally, return the new head.

DSA C++

struct Node {
    int data;
    Node* next;
};

Node node1 = {10, nullptr};
Node node2 = {20, nullptr};
Node node3 = {30, nullptr};
Node node4 = {40, nullptr};
Node node5 = {50, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;

Node* head = &node1;

Node* reverseList(Node* head) {
    // Your code here
}

Hint

Use the base case to return head if it is nullptr or the last node. Then call reverseList recursively on head->next. After recursion, reverse the link by setting head->next->next = head and break the old link with head->next = nullptr. Return the new head.

4

Print the reversed linked list

Call reverseList with head and store the result back in head. Then use a while loop to print each node's data followed by ' -> '. After the loop, print 'null' to show the end of the list.

DSA C++

struct Node {
    int data;
    Node* next;
};

Node node1 = {10, nullptr};
Node node2 = {20, nullptr};
Node node3 = {30, nullptr};
Node node4 = {40, nullptr};
Node node5 = {50, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;

Node* head = &node1;

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

// Call reverseList and print the reversed list
// Your code here

Hint

Call reverseList(head) and assign it back to head. Then use a while loop to print each node's data followed by ' -> '. After the loop, print 'null'.

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