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

Time Complexity: Reverse a Singly Linked List Iterative

O(n)

Understanding Time Complexity

We want to know how the time needed to reverse a linked list changes as the list gets bigger.

Specifically, how many steps does it take to reverse all the nodes one by one?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Reverse a singly linked list iteratively
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;
    struct Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
    

This code reverses the links between nodes in a singly linked list one by one until the entire list is reversed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once.
• How many times: Exactly once per node, so as many times as there are nodes in the list.

How Execution Grows With Input

Each node is visited once, so the total steps grow directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the list size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to reverse the list grows in a straight line with the number of nodes.

Common Mistake

[X] Wrong: "Reversing a linked list takes more than linear time because of pointer changes."

[OK] Correct: Each node is visited only once, and pointer changes happen in constant time per node, so total time is linear.

Interview Connect

Understanding this linear time reversal is a key skill that shows you can work with linked lists efficiently.

Self-Check

"What if we used recursion instead of iteration? How would the time complexity change?"