Reverse a Singly Linked List Recursive in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Reverse on a 3-Node List

What is the printed state of the linked list after calling the recursive reverse function on this list?

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

DSA C

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

Node* reverseRecursive(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* rest = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

// After calling reverseRecursive on list 1->2->3->NULL, print the list

A 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> null

C 3 -> 1 -> 2 -> null

D 2 -> 3 -> 1 -> null

💡 Hint

Think about how the recursion reaches the last node and then reverses the links step by step.

The recursive function goes to the last node (3), then reverses the links so that 3 points to 2, and 2 points to 1, and finally 1 points to NULL. So the list is reversed as 3 -> 2 -> 1 -> null.

❓ Predict Output

intermediate

Output of Recursive Reverse on Single Node List

What is the printed state of the linked list after calling the recursive reverse function on a single-node list?

Initial list: 5 -> null

DSA C

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

Node* reverseRecursive(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* rest = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

// After calling reverseRecursive on list 5->NULL, print the list

A null

B 5 -> null

C 5 -> 5 -> null

D Error: segmentation fault

💡 Hint

A single node reversed is still the same node.

The base case returns the head immediately if the list has only one node or is empty, so the list remains unchanged.

🔧 Debug

advanced

Identify the Bug in Recursive Reverse Function

What error will this recursive reverse function cause when called on a list with multiple nodes?

DSA C

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

Node* reverseRecursive(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* rest = reverseRecursive(head->next);
    head->next = NULL;
    head->next->next = head;
    return rest;
}

A Segmentation fault (runtime error)

B No error, works correctly

C Compilation error: invalid assignment

D Infinite recursion

💡 Hint

Look carefully at the order of pointer assignments after recursion.

The line 'head->next = NULL;' sets head->next to NULL before 'head->next->next = head;' is executed, so head->next is NULL and accessing head->next->next causes a segmentation fault.

❓ Predict Output

advanced

Output of Recursive Reverse on 4-Node List

What is the printed state of the linked list after calling the recursive reverse function on this list?

Initial list: 10 -> 20 -> 30 -> 40 -> null

DSA C

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

Node* reverseRecursive(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* rest = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

// After calling reverseRecursive on list 10->20->30->40->NULL, print the list

A 40 -> 20 -> 30 -> 10 -> null

B 10 -> 20 -> 30 -> 40 -> null

C 40 -> 30 -> 20 -> 10 -> null

D 30 -> 40 -> 20 -> 10 -> null

💡 Hint

The recursive function reverses the list by changing the next pointers step by step from the end.

The recursion reaches the last node (40), then reverses the links so that 40 points to 30, 30 points to 20, 20 points to 10, and 10 points to NULL.

🧠 Conceptual

expert

Why Does Recursive Reverse Use head->next->next = head?

In the recursive reverse function for a singly linked list, why do we assign 'head->next->next = head;' instead of 'head->next = head;'?

A Because 'head->next->next = head;' sets the current node's next to NULL automatically.

B Because 'head->next = head;' is invalid syntax in C and causes a compilation error.

C Because 'head->next = head;' deletes the next node from memory.

D Because 'head->next->next = head;' reverses the link direction, making the next node point back to the current node, while 'head->next = head;' would create a cycle.

💡 Hint

Think about how pointers must be reversed to flip the list direction.

The assignment 'head->next->next = head;' makes the next node point back to the current node, reversing the link. Assigning 'head->next = head;' would make the current node point to itself, causing a cycle.

Practice

1. What is the main idea behind reversing a singly linked list using recursion?

easy

A. Use a stack to store nodes and pop them in reverse order

B. Reverse the rest of the list and then fix the first node's next pointer

C. Swap the data values of nodes from start to end

D. Iterate through the list and reverse pointers one by one

Solution

1. Step 1: Understand recursion on linked list

   Recursion reverses the list from the second node onward first.

2. Step 2: Fix the first node's next pointer

   After recursion returns, the first node's next pointer is set to null and the previous node points back to it.

3. Final Answer:

   Reverse the rest of the list and then fix the first node's next pointer -> Option B

4. Quick Check:

   Recursive reversal = Reverse rest + fix first [OK]

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

Common Mistakes:

• Trying to swap node data instead of pointers
• Not setting the first 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 == NULL) return NULL;

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

C. if (head == NULL || head->next == NULL) return head;

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

Solution

1. Step 1: Identify base cases for recursion

   Base case must handle empty list and single node list to stop recursion.

2. Step 2: Choose correct condition

   Condition 'head == NULL || head->next == NULL' covers both empty and single node cases.

3. Final Answer:

   if (head == NULL || head->next == NULL) return head; -> Option C

4. Quick Check:

   Base case = empty or single node [OK]

Hint: Base case stops recursion on empty or single node [OK]

Common Mistakes:

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

3. What will be the output linked list after reversing recursively the list: 1 -> 2 -> 3 -> NULL?

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 recursive reversal

   Recursion reverses from last node back: 3 becomes new head, 2 points to 1, 1 points to NULL.

2. Step 2: Confirm final list order

   Final reversed list is 3 -> 2 -> 1 -> NULL.

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option D

4. Quick Check:

   Reverse(1->2->3) = 3->2->1 [OK]

Hint: Last node becomes new head after recursion [OK]

Common Mistakes:

• Assuming original order remains
• Mixing node values instead of pointers
• Forgetting to set last node's next to NULL

4. Identify the error in this recursive reverse function snippet:

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

medium

A. head->next is set to head instead of NULL causing a cycle

B. Missing base case for empty list

C. Incorrect return value; should return head

D. No recursive call made

Solution

1. Step 1: Analyze pointer assignments

   head->next->next = head correctly points next node back to current node.

2. Step 2: Identify incorrect pointer reset

   head->next = head wrongly points current node's next to itself, causing a cycle instead of NULL.

3. Final Answer:

   head->next is set to head instead of NULL causing a cycle -> Option A

4. Quick Check:

   head->next must be NULL, not head [OK]

Hint: Set head->next to NULL to avoid cycles [OK]

Common Mistakes:

• Setting head->next to head causing infinite loop
• Forgetting to return the new head
• Not handling base case properly

5. Given a singly linked list with nodes containing values 10 -> 20 -> 30 -> 40 -> NULL, what will be the printed output after applying this recursive reverse function?

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

void printList(Node* head) {
  while (head) {
    printf("%d -> ", head->data);
    head = head->next;
  }
  printf("NULL\n");
}

int main() {
  // List creation omitted for brevity
  Node* reversed = reverse(head);
  printList(reversed);
}

hard

A. 40 -> 30 -> 20 -> 10 -> NULL

B. 10 -> 20 -> 30 -> 40 -> NULL

C. NULL

D. 40 -> 20 -> 30 -> 10 -> NULL

Solution

1. Step 1: Trace recursive reversal on list 10->20->30->40

   Recursion reverses from last node: 40 becomes new head, pointers reversed stepwise.

2. Step 2: Confirm print output

   Print function outputs nodes in order: 40 -> 30 -> 20 -> 10 -> NULL.

3. Final Answer:

   40 -> 30 -> 20 -> 10 -> NULL -> Option A

4. Quick Check:

   Reverse(10->20->30->40) = 40->30->20->10 [OK]

Hint: Last node becomes head; print from new head [OK]

Common Mistakes:

• Assuming original order remains after reverse
• Forgetting to set last node's next to NULL
• Confusing print output with input list