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.