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 understand how the time needed to add two numbers as linked lists grows as the numbers get longer.

How does the work change when the linked lists have more digits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
    }
    return dummy.next;
}
    

This code adds two numbers where each digit is a node in a linked list, digit by digit, carrying over when needed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that goes through each node of both 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 loop cycles
100	About 100 loop cycles
1000	About 1000 loop cycles

Pattern observation: The work grows directly with the number of digits; doubling digits roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The time complexity is O(n²) because we create new nodes inside the loop."

[OK] Correct: Creating a new node is a constant time action done once per loop cycle, so it does not multiply the work; the loop itself runs only once per digit.

Interview Connect

Understanding this linear time complexity helps you explain how your solution scales with input size, a key skill interviewers look for.

Self-Check

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

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" mainly involve?

easy

A. Sorting two linked lists in ascending order

B. Adding digits node by node from two linked lists representing numbers

C. Finding the middle node of a linked list

D. Reversing a linked list

Solution

1. Step 1: Understand the problem context

   The problem involves two linked lists where each node contains a single digit. These digits represent numbers in reverse order.

2. Step 2: Identify the required operation

   We need to add these two numbers digit by digit, managing carry, and return the sum as a linked list.

3. Final Answer:

   Adding digits node by node from two linked lists representing numbers -> Option B

4. Quick Check:

   Adding digits node by node = B [OK]

Hint: Focus on digit-wise addition with carry [OK]

Common Mistakes:

• Confusing addition with sorting
• Ignoring carry during addition
• Assuming numbers are stored in forward order

2. Which of the following C# code snippets correctly initializes a linked list node for this problem?

easy

A. ListNode node = new ListNode();

B. ListNode node = ListNode(5);

C. ListNode node = new ListNode(5);

D. ListNode node = new ListNode.val(5);

Solution

1. Step 1: Recall C# object initialization syntax

   In C#, to create an object, use the 'new' keyword followed by the constructor call with parameters.

2. Step 2: Check each option for correct syntax

   A creates node with default val=0, incorrect for val=5. B misses 'new'. C: ListNode node = new ListNode(5); is correct. D has invalid syntax.

3. Final Answer:

   ListNode node = new ListNode(5); -> Option C

4. Quick Check:

   Use 'new' keyword with constructor = C [OK]

Hint: Use 'new' keyword to create objects in C# [OK]

Common Mistakes:

• Omitting 'new' keyword
• Incorrect constructor call syntax
• Trying to assign value directly without constructor

3. What will be the output linked list after adding these two numbers represented as linked lists?

List1: 2 -> 4 -> 3 -> null (represents 342)
List2: 5 -> 6 -> 4 -> null (represents 465)

Code snippet:

var result = AddTwoNumbers(l1, l2);
PrintList(result);

What is the printed linked list?

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 2 -> 4 -> 3 -> 5 -> 6 -> 4 -> null

Solution

1. Step 1: Add digits node by node with carry

   Adding 2+5=7 (carry 0), 4+6=10 (carry 1), 3+4=7 plus carry 1 = 8.

2. Step 2: Form the resulting linked list

   The result is 7 -> 0 -> 8 -> null, representing 807.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

4. Quick Check:

   342 + 465 = 807 = 7->0->8 [OK]

Hint: Add digits with carry, store result digit-wise [OK]

Common Mistakes:

• Not handling carry correctly
• Appending nodes instead of summing digits
• Confusing order of digits

4. Identify the error in this C# method snippet for adding two numbers represented as linked lists:

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    while (l1 != null || l2 != null) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
}

medium

A. Returning dummy instead of dummy.next

B. Incorrect initialization of carry variable

C. Wrong use of ternary operator for x and y

D. Missing check to add carry node after loop ends

Solution

1. Step 1: Analyze loop and carry handling

   The loop adds digits and updates carry, but after loop ends, if carry > 0, it must be added as a new node.

2. Step 2: Identify missing carry node addition

   Code does not add a node for leftover carry after loop, which causes incorrect result for sums like 5+5=10.

3. Final Answer:

   Missing check to add carry node after loop ends -> Option D

4. Quick Check:

   Carry node after loop missing = A [OK]

Hint: Always add leftover carry node after loop [OK]

Common Mistakes:

• Forgetting to add carry node after loop
• Returning dummy instead of dummy.next
• Incorrect carry initialization

5. Given two linked lists representing numbers in reverse order:
List1: 9 -> 9 -> 9 -> 9 -> null (represents 9999)
List2: 1 -> null (represents 1)

What will be the resulting linked list after adding them using the standard algorithm?

hard

A. 0 -> 0 -> 0 -> 0 -> 1 -> null

B. 1 -> 0 -> 0 -> 0 -> 0 -> null

C. 0 -> 0 -> 0 -> 0 -> null

D. 9 -> 9 -> 9 -> 9 -> 1 -> null

Solution

1. Step 1: Add digits with carry step-by-step

   9+1=10 (digit 0, carry 1), then 9+0+1=10 (digit 0, carry 1) repeated for next two nodes.

2. Step 2: Add final carry node

   After last addition, carry is 1, so add new node with value 1 at the end.

3. Final Answer:

   0 -> 0 -> 0 -> 0 -> 1 -> null -> Option A

4. Quick Check:

   9999 + 1 = 10000 = 0->0->0->0->1 [OK]

Hint: Carry can extend list length by one node [OK]

Common Mistakes:

• Ignoring carry after last node
• Appending digits without carry
• Misplacing the carry node