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

Concept Flow - Add Two Numbers Represented as Linked List

Start with two linked lists

↓

Initialize carry = 0, dummy head node

↓

Traverse both lists simultaneously

↓

Add digits + carry

↓

Create new node with sum % 10

↓

Update carry = sum / 10

↓

Move to next nodes

↓

Repeat until both lists and carry are empty

↓

Return list starting after dummy head

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

Execution Sample

DSA Java

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 + (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
    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;
}

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	Digits Added	Sum	Carry	New Node Created	Visual State
1	Add first digits	2 + 5 + carry 0	7	0	7	7 -> null
2	Add second digits	4 + 6 + carry 0	10	1	0	7 -> 0 -> null
3	Add third digits	3 + 4 + carry 1	8	0	8	7 -> 0 -> 8 -> null
4	Add fourth digits	0 + 9 + carry 0	9	0	9	7 -> 0 -> 8 -> 9 -> null
5	No more digits in l1 and l2, carry 0	Stop	-	-	-	Final list: 7 -> 0 -> 8 -> 9 -> null

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we continue the loop even if one list is null?

Because the other list may still have digits or there may be a carry to add, as shown in steps 3 and 4 where l1 is null but l2 and carry are not.

Why do we create a dummy head node?

The dummy head simplifies adding new nodes without checking if the list is empty. The final result starts from dummy.next as seen in the code and final visual state.

How is the carry handled when sum is 10 or more?

Carry is sum divided by 10 (integer division). For example, in step 2 sum is 10, carry becomes 1, and new node value is 0 (sum % 10).

Visual Quiz - 3 Questions

Look at the execution table, what is the carry value after step 2?

A 1

B 2

C 0

D 10

💡 Hint

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

At which step does the linked list first include a node with value 8?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'New Node Created' and 'Visual State' columns in the execution_table.

If the carry was not included in the sum calculation, what would happen at step 3?

A Sum would be 4 instead of 8

B Sum would be 7 instead of 8

C Sum would be 3 instead of 8

D Sum would be 8 as usual

💡 Hint

Refer to the 'Digits Added' column at step 3 and consider carry's effect.

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 dummy head node and a carry of zero. We traverse both lists simultaneously, adding corresponding digits plus the carry. The sum's last digit becomes a new node, and the carry is updated for the next addition. We continue until both lists are fully traversed and no carry remains. The result is a new linked list representing the sum. Key points include handling different list lengths, using a dummy head to simplify list building, and managing carry correctly.

Practice

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

easy

A. Reversing a linked list

B. Sorting two linked lists in ascending order

C. Finding the middle node of a linked list

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

Solution

1. Step 1: Understand the problem context

   The problem involves two linked lists where each node contains a digit of a number, stored in reverse order.

2. Step 2: Identify the required operation

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

3. Final Answer:

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

4. Quick Check:

   Adding digits node by node = D [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 Java code snippets correctly initializes a new node for a singly linked list representing a digit?

easy

A. ListNode node = ListNode(5);

B. ListNode node = new ListNode(); node.next = 5;

C. ListNode node = new ListNode(5);

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

Solution

1. Step 1: Recall Java object creation syntax

   In Java, to create a new object, use the 'new' keyword followed by the constructor call with parameters.

2. Step 2: Check each option for correct syntax

   ListNode node = new ListNode(5); uses 'new ListNode(5);' which is correct. ListNode node = ListNode(5); misses 'new'. ListNode node = new ListNode(); node.next = 5; incorrectly sets next instead of val. ListNode node = new ListNode.val(5); is invalid syntax.

3. Final Answer:

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

4. Quick Check:

   Java new object syntax = B [OK]

Hint: Use 'new' keyword with constructor for object creation [OK]

Common Mistakes:

• Omitting 'new' keyword
• Incorrect constructor call syntax
• Trying to call constructor like a method without 'new'
• Confusing node.val and node.next

3. What is the output linked list after adding the two numbers represented by these linked lists? List 1: 2 -> 4 -> 3 -> null (represents 342) List 2: 5 -> 6 -> 4 -> null (represents 465)

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

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: Construct the resulting linked list

   Digits are 7 (units), 0 (tens), 8 (hundreds), so linked list is 7 -> 0 -> 8 -> null.

3. Final Answer:

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

4. Quick Check:

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

Hint: Add digits with carry, build new nodes [OK]

Common Mistakes:

• Ignoring carry in addition
• Appending nodes incorrectly
• Mixing digit order in output

4. Identify the bug in this code snippet for adding two numbers represented as linked lists:

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

medium

A. The carry is not calculated correctly

B. The while loop should use '||' instead of '&&' to handle different length lists

C. The dummy node is not initialized properly

D. The function does not return the correct node

Solution

1. Step 1: Analyze the loop condition

   The loop uses '&&' which stops when either list ends, missing remaining nodes of longer list.

2. Step 2: Correct loop condition to '||'

   Using '||' ensures the loop continues until both lists are fully processed, handling different lengths correctly.

3. Final Answer:

   The while loop should use '||' instead of '&&' to handle different length lists -> Option B

4. Quick Check:

   Loop condition must cover all nodes = A [OK]

Hint: Use '||' to process all nodes in both lists [OK]

Common Mistakes:

• Using '&&' causing early loop exit
• Not handling carry after loop
• Not advancing pointers correctly

5. Given two linked lists representing numbers in reverse order, how would you modify the addition algorithm to handle the case where the input lists are extremely long (millions of nodes) and memory is limited?

hard

A. Use iterative addition with constant extra space and process nodes one by one

B. Convert linked lists to integers, add, then convert back to linked list

C. Store all digits in arrays before adding to optimize speed

D. Reverse both lists first, add, then reverse the result

Solution

1. Step 1: Consider memory constraints with large inputs

   Converting to integers or arrays requires large memory, not feasible for millions of nodes.

2. Step 2: Use iterative addition with constant extra space

   Process nodes one by one, create result nodes on the fly, and avoid storing entire numbers in memory.

3. Final Answer:

   Use iterative addition with constant extra space and process nodes one by one -> Option A

4. Quick Check:

   Iterative node-wise addition saves memory = C [OK]

Hint: Add nodes one by one without full number conversion [OK]

Common Mistakes:

• Trying to convert entire list to integer causing overflow
• Using extra arrays increasing memory usage
• Reversing lists unnecessarily increasing complexity