Reverse a Singly Linked List Recursive in DSA C

Mental Model

We flip the direction of each link by going to the end first, then changing pointers on the way back.

Analogy: Imagine unstacking a pile of plates one by one to the bottom, then stacking them back up in reverse order.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

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

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

Step 1: call reverse on node 1, which calls reverse on node 2

head -> 1 -> 2 -> 3 -> null ↑ (recursion goes deeper)

Why: We need to reach the last node before changing links

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

head -> 1 -> 2 -> 3 -> null ↑ (at last node)

Why: Last node becomes new head of reversed list

Step 3: node 2's next (3) points back to node 2, node 2's next set to null

head -> 1 -> 2 -> null
3 -> 2 -> null (reversed part)

Why: Flip the link between node 2 and 3

Step 4: node 1's next (2) points back to node 1, node 1's next set to null

head -> 1 -> null
2 -> 1 -> null
3 -> 2 -> 1 -> null (fully reversed)

Why: Flip the link between node 1 and 2

Step 5: return new head node 3 up the recursion

3 -> 2 -> 1 -> null

Why: Return the new head of reversed list

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Recursive reverse function
Node* reverseRecursive(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head; // base case: empty or single node
    }
    Node* newHead = reverseRecursive(head->next); // reverse rest
    head->next->next = head; // flip link
    head->next = NULL; // set current next to null
    return newHead; // return new head
}

// Print list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d", curr->data);
        if (curr->next != NULL) printf(" -> ");
        curr = curr->next;
    }
    printf(" -> null\n");
}

int main() {
    // Create list 1 -> 2 -> 3 -> null
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    printf("Original list: ");
    printList(head);

    head = reverseRecursive(head);

    printf("Reversed list: ");
    printList(head);

    return 0;
}

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

base case: stop recursion at empty or last node

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

recursively reverse the rest of the list

head->next->next = head;

flip the link so next node points back to current

head->next = NULL;

set current node's next to null to avoid cycle

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 recursive is simpler to write and understand

Edge Cases

empty list (head == NULL)

function returns NULL immediately without error

DSA C

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

single node list

function returns the single node as is

DSA C

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

When to Use This Pattern

When you see a problem asking to reverse a linked list and recursion is allowed, use recursive reversal to simplify pointer changes by handling the tail first.

Common Mistakes

Mistake: Not setting head->next to NULL after flipping the link, causing cycles
Fix: Always set head->next = NULL after reversing the rest and flipping the link

Summary

Reverses a singly linked list by recursively flipping links from the end to the front.

Use when you want a clean, elegant solution to reverse a linked list using recursion.

The key is to reverse the rest first, then flip the current node's link back.

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