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.