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

Time Complexity: Reverse a Singly Linked List Iterative

O(n)

Understanding Time Complexity

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

Specifically, how does the number of steps grow when we reverse the list one node at a time?

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_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

This code reverses a singly linked list by changing the direction of the links 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 n times for n nodes.

How Execution Grows With Input

As the list gets longer, the number of steps grows 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: The steps increase in a straight line as the list size grows.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Reversing the list takes constant time because we just change pointers."

[OK] Correct: Even though each pointer change is quick, we must do it for every node, so the total time grows with the list size.

Interview Connect

Understanding this time complexity helps you explain why reversing a list is efficient and what to expect as input grows, a useful skill in many coding challenges.

Self-Check

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