Add Two Numbers Represented as Linked List in DSA Python - Time & Space Complexity

Time Complexity: Add Two Numbers Represented as Linked List

O(n)

Understanding Time Complexity

We want to understand how the time to add two numbers stored as linked lists grows as the numbers get longer.

How does the number of steps change when the linked lists have more digits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def addTwoNumbers(l1, l2):
    carry = 0
    dummy = ListNode()
    current = dummy
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)
        current = current.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next
    

This code adds two numbers digit by digit, handling carry, and returns the sum as a linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that goes through each node of the linked lists.
• How many times: It runs once for each digit in the longer linked list, plus one extra if there is a carry at the end.

How Execution Grows With Input

As the number of digits (nodes) increases, the loop runs more times, roughly once per digit.

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

Pattern observation: The number of steps grows directly with the number of digits.

Final Time Complexity

Time Complexity: O(n)

This means the time to add the numbers grows linearly with the number of digits.

Common Mistake

[X] Wrong: "The time depends on the value of the numbers, not their length."

[OK] Correct: The code processes each digit once, so the length of the list matters, not the number's size.

Interview Connect

Understanding this helps you explain how linked list traversal affects performance, a key skill in many coding challenges.

Self-Check

"What if the numbers were stored in forward order instead of reverse? How would the time complexity change?"