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

Time Complexity: Add Two Numbers Represented as Linked List

O(n)

Understanding Time Complexity

We want to know 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.

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    struct ListNode* current = dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) { sum += l1->val; l1 = l1->next; }
        if (l2) { sum += l2->val; l2 = l2->next; }
        carry = sum / 10;
        current->next = malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = sum % 10;
        current->next = NULL;
    }
    return dummy->next;
}
    

This code adds two numbers digit by digit, moving through each linked list once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves 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

Each step processes one digit from the input lists, so the total steps grow directly with the number of digits.

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

Pattern observation: The number of steps grows in a straight line as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to add the numbers grows directly with the number of digits in the longer list.

Common Mistake

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

[OK] Correct: The code processes each digit once, so the time depends on how many digits there are, not the actual number values.

Interview Connect

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

Self-Check

"What if the input lists were doubly linked lists? How would the time complexity change?"