Reverse a Singly Linked List Recursive in DSA C - Time & Space Complexity

Time Complexity: Reverse a Singly Linked List Recursive

O(n)

Understanding Time Complexity

We want to understand how the time needed to reverse a linked list grows as the list gets longer.

Specifically, how many steps does the recursive method take as the list size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code reverses a singly linked list by calling itself on the next node until it reaches the end, then rewires the links backward.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call on the next node of the list.
• How many times: Once for each node in the list, so n times for a list of size n.

How Execution Grows With Input

Each node causes one recursive call, so the number of steps grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 recursive calls and rewiring steps
100	About 100 recursive calls and rewiring steps
1000	About 1000 recursive calls and rewiring steps

Pattern observation: The work grows linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to reverse the list grows in direct proportion to the number of nodes.

Common Mistake

[X] Wrong: "Recursive reversal is faster than iterative reversal because recursion is magical."

[OK] Correct: Both recursive and iterative methods visit each node once, so they take similar time. Recursion adds extra overhead from function calls but does not reduce the total steps.

Interview Connect

Understanding recursive reversal helps you think about how recursion works on linked structures, a key skill for many coding problems.

Self-Check

"What if we changed the recursion to an iterative loop? How would the time complexity change?"