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

Time Complexity: Reverse a Singly Linked List Recursive

O(n)

Understanding Time Complexity

When reversing a singly linked list using recursion, we want to know how the time needed grows as the list gets longer.

We ask: How many steps does it take to reverse a list of size n?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

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

• Primary operation: Recursive call on each node of the list.
• How many times: Exactly once per node, so n times for a list of size n.

How Execution Grows With Input

Each node causes one recursive call, so the total steps grow 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: "Recursion makes this slower than a loop, so it must be more than O(n)."

[OK] Correct: Each node is still visited once, so recursion does not add extra visits; it just changes how the calls are made.

Interview Connect

Understanding recursive reversal shows you can think about problems in different ways and handle linked lists confidently, a key skill in many coding challenges.

Self-Check

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