Add Two Numbers Represented as Linked List in DSA C# - Execution Trace

Concept Flow - Add Two Numbers Represented as Linked List

Start with two linked lists

↓

Initialize carry = 0 and dummy head

↓

Traverse both lists node by node

↓

Sum node values + carry

↓

Create new node with sum % 10

↓

Update carry = sum / 10

↓

Move to next nodes in both lists

↓

Repeat until both lists and carry are empty

↓

Return linked list starting after dummy head

We add digits from two linked lists one by one, keep track of carry, and build a new list with the sum digits.

Execution Sample

DSA C#

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

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

Execution Table

Step	Operation	l1 Node Value	l2 Node Value	Sum	Carry	New Node Value	Linked List State
1	Add 2 + 5 + carry 0	2	5	7	0	7	7 -> null
2	Add 4 + 6 + carry 0	4	6	10	1	0	7 -> 0 -> null
3	Add 3 + 4 + carry 1	3	4	8	0	8	7 -> 0 -> 8 -> null
4	l1 and l2 are null, carry 0	null	null	0	0	none	7 -> 0 -> 8 -> null

💡 Both lists are fully traversed and carry is 0, so addition is complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
carry	0	0	1	0	0
l1	2 -> 4 -> 3	4 -> 3	3	null	null
l2	5 -> 6 -> 4	6 -> 4	4	null	null
current (new list)	dummy	7	0	8	8

Key Moments - 3 Insights

Why do we continue the loop when both lists are null but carry is not zero?

Because carry can add an extra digit to the result. For example, if the last sum is 15, carry is 1 and we must add a new node with 1. See execution_table step 2 where carry is 1 after sum 10.

Why do we use a dummy head node for the result list?

Dummy head simplifies adding new nodes without checking if the list is empty. It lets us return dummy.next at the end as the real head. See variable_tracker current starting at dummy.

How do we handle different lengths of the two input lists?

We treat missing nodes as 0 by using (l1 != null ? l1.val : 0) and (l2 != null ? l2.val : 0). This lets us add digits even if one list is shorter. See execution_table step 4 where both nodes are null but carry is checked.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the carry value after adding nodes?

A 2

B 0

C 1

D None

💡 Hint

Check the 'Carry' column in execution_table row for step 2.

At which step does the linked list state become '7 -> 0 -> 8 -> null'?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look at the 'Linked List State' column in execution_table for each step.

If the first list was longer, how would the loop condition change?

A It would stop earlier

B It would continue until the longer list ends and carry is zero

C It would ignore the longer list's extra nodes

D It would cause an error

💡 Hint

Refer to the loop condition in the code and how l1, l2, and carry control continuation.

Concept Snapshot

Add Two Numbers as Linked Lists:
- Traverse both lists node by node
- Sum digits + carry
- Create new node with sum % 10
- Update carry = sum / 10
- Continue until both lists and carry are done
- Return list after dummy head

Full Transcript

This concept adds two numbers represented by linked lists digit by digit. We start with a carry of zero and a dummy head node to build the result list. At each step, we add the current digits from both lists plus the carry. We create a new node with the digit part of the sum and update the carry for the next step. We move forward in both lists until all digits and carry are processed. The dummy head helps return the final sum list easily. This method handles different list lengths and carry overs correctly.

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