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

Reverse a Singly Linked List Recursively

📖 Scenario: You are working on a simple phone contact list app. The contacts are stored in a singly linked list in the order they were added. You want to add a feature to reverse the contact list so the newest contact appears first.

🎯 Goal: Build a program in C that creates a singly linked list of contacts, then reverses the list using a recursive function, and finally prints the reversed list.

📋 What You'll Learn

Define a struct called Node with an integer data and a pointer next to the next node

Create a linked list with exactly three nodes containing data 10, 20, and 30 in that order

Write a recursive function called reverseRecursive that takes a pointer to the head node and returns the new head after reversing

Print the reversed linked list data values separated by arrows like 30 -> 20 -> 10 -> NULL

💡 Why This Matters

🌍 Real World

Reversing linked lists is useful in many applications like undo features, reversing playback order, or processing data in reverse order.

💼 Career

Understanding linked list reversal is a common interview question and helps in mastering pointers and recursion in C programming.

1

Create the initial linked list

Define a struct called Node with an integer data and a pointer next. Then create three nodes with data 10, 20, and 30 linked in that order. Store the head node pointer in a variable called head.

DSA C

// Define struct Node and create linked list with nodes 10, 20, 30
// Your code here

Hint

Remember to link each node's next pointer to the next node, and the last node's next should be NULL.

2

Add the recursive reverse function declaration

Declare a recursive function called reverseRecursive that takes a pointer to Node called head and returns a pointer to Node. Add only the function prototype above main.

DSA C

#include 
#include 

// Declare reverseRecursive function prototype here
// Your code here

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

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 10;
    head->next = malloc(sizeof(Node));
    head->next->data = 20;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;
    return 0;
}

Hint

The function prototype should be placed before main and match the signature exactly.

3

Implement the recursive reverse function

Write the full definition of the function reverseRecursive that reverses the linked list recursively and returns the new head pointer.

DSA C

#include 
#include 

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

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

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 10;
    head->next = malloc(sizeof(Node));
    head->next->data = 20;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;
    return 0;
}

Hint

Use the base case when head is NULL or head->next is NULL. Then recursively reverse the rest and fix the links.

4

Reverse the list and print the result

In main, call reverseRecursive with head and update head to the returned pointer. Then print the reversed list nodes' data separated by -> and ending with NULL.

DSA C

#include 
#include 

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

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

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 10;
    head->next = malloc(sizeof(Node));
    head->next->data = 20;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;

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

    return 0;
}

Hint

After reversing, use a loop to print each node's data followed by ->. End with NULL and a newline.

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