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.