Reverse a Singly Linked List Recursive in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the list is empty or has one node.

DSA C

if (head == NULL || head->[1] == NULL) {
    return head;
}

Drag options to blanks, or click blank then click option'

Avalue

Bprev

Cdata

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' in a singly linked list.

Checking the data value instead of the next pointer.

The base case for recursion checks if the list is empty or has only one node by checking if head or head->next is NULL.

2fill in blank

medium

Complete the code to recursively reverse the rest of the list.

DSA C

struct Node* rest = [1](head->next);

Drag options to blanks, or click blank then click option'

AprintList

BfreeList

CreverseList

DdeleteList

Attempts:

3 left

💡 Hint

Common Mistakes

Using a function that frees or deletes the list instead of reversing.

Calling a print function instead of recursive reverse.

The function calls itself recursively to reverse the rest of the list starting from head->next.

3fill in blank

hard

Fix the error in setting the next node's next pointer to the current head.

DSA C

head->next->[1] = head;

Drag options to blanks, or click blank then click option'

Aprev

Bnext

Cdata

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' which does not exist in singly linked list nodes.

Trying to assign to data or value fields.

To reverse the link, set head->next->next to head, changing the direction of the pointer.

4fill in blank

hard

Fill both blanks to complete the recursive reversal and break the old link.

DSA C

head->[1] = NULL;
return [2];

Drag options to blanks, or click blank then click option'

Anext

Brest

Cprev

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Returning head instead of rest.

Not setting head->next to NULL causing cycles.

After reversing, set head->next to NULL to break the old link and return the new head stored in rest.

5fill in blank

hard

Fill all three blanks to complete the full recursive reverse function.

DSA C

struct Node* reverseList(struct Node* head) {
    if (head == NULL || head->[1] == NULL) {
        return head;
    }
    struct Node* [2] = reverseList(head->next);
    head->next->[3] = head;
    head->next = NULL;
    return [2];
}

Drag options to blanks, or click blank then click option'

Anext

Brest

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' which is not part of singly linked list node.

Not breaking the old link by setting head->next to NULL.

The function checks if head or head->next is NULL, recursively reverses the rest, sets head->next->next to head, breaks old link, and returns new head.

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