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

Concept Flow - Add Two Numbers Represented as Linked List

Start at head of List1 and List2

↓

Add digits + carry

↓

Create new node with sum % 10

↓

Move to next nodes in List1 and List2

↓

Carry = Math.floor(sum / 10)

↓

Are nodes or carry left?

No→End

↩Back to Add digits + carry

We add digits from both lists node by node, carry over if sum > 9, create new nodes for result, and continue until all digits and carry are processed.

Execution Sample

DSA Typescript

function addTwoNumbers(l1, l2) {
  let carry = 0;
  let dummy = new ListNode(0);
  let current = dummy;
  while (l1 || l2 || carry) {
    let sum = (l1?.val || 0) + (l2?.val || 0) + carry;
    carry = Math.floor(sum / 10);
    current.next = new ListNode(sum % 10);
    current = current.next;
    l1 = l1?.next || null;
    l2 = 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 new linked list.

Execution Table

Step	Operation	Nodes in List1	Nodes in List2	Sum	Carry	New Node Created	Result List Visual
1	Add 2 + 5 + 0	2 -> 4 -> 3	5 -> 6 -> 4	7	0	7	7 -> null
2	Add 4 + 6 + 0	4 -> 3	6 -> 4	10	1	0	7 -> 0 -> null
3	Add 3 + 4 + 1	3	4	8	0	8	7 -> 0 -> 8 -> null
4	No nodes left, carry 0	null	null	0	0	none	7 -> 0 -> 8 -> null

💡 No nodes left in both lists and carry is 0, so addition ends.

Variable Tracker

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

Key Moments - 3 Insights

Why do we add carry to the sum each time?

Because the previous addition might have produced a carry (like 10 or more), which must be added to the next digit sum. See execution_table rows 2 and 3 where carry is 1.

What happens if one list is longer than the other?

We treat missing nodes as 0. For example, if l1 ends but l2 still has nodes, we add 0 + l2's digit + carry. This is shown in the code with (l1?.val || 0).

Why do we create a dummy node at the start?

The dummy node helps to easily build the result list without checking if it's the first node. The real result starts from dummy.next. This avoids special cases.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the carry value after addition?

A 1

B 2

C 0

D None

💡 Hint

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

At which step does the result list first contain the node with value 8?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

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

If the first list was longer, how would the code handle extra nodes?

A It would cause an error

B It would ignore extra nodes

C It would add them with carry and 0 for missing second list nodes

D It would stop early

💡 Hint

See the code line using (l1?.val || 0) and the loop condition (l1 || l2 || carry).

Concept Snapshot

Add Two Numbers as Linked Lists:
- Traverse both lists node by node
- Sum digits + carry
- Create new node with sum % 10
- Carry = Math.floor(sum / 10)
- Continue until no nodes and carry
- Use dummy head to simplify list building

Full Transcript

To add two numbers represented as linked lists, we start from the heads of both lists. We add the digits of the current nodes plus any carry from the previous addition. We create a new node with the digit part of the sum (sum modulo 10) and update the carry (Math.floor(sum divided by 10)). We move to the next nodes in both lists. If one list is shorter, we treat missing nodes as zero. We continue this process until both lists are fully traversed and no carry remains. A dummy node helps to build the result list easily. The final linked list represents the sum of the two numbers in reverse order.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" ask you to do?

easy

A. Find the difference between two numbers stored as strings.

B. Add two numbers where each digit is stored in a node of a linked list, and return the sum as a linked list.

C. Sort two linked lists and merge them into one sorted list.

D. Multiply two numbers stored in arrays and return the product as an array.

Solution

1. Step 1: Understand the input format

   The numbers are given as linked lists where each node contains a single digit, and digits are stored in reverse order.

2. Step 2: Understand the required output

   You must add these two numbers digit by digit and return the sum as a linked list in the same reversed format.

3. Final Answer:

   Add two numbers digit-wise from linked lists and return sum as linked list -> Option B

4. Quick Check:

   Adding digits node by node = Add two numbers as linked lists [OK]

Hint: Add digits node by node with carry, return linked list [OK]

Common Mistakes:

• Confusing input format as normal integers
• Returning sum as integer instead of linked list
• Ignoring carry over digits

2. Which TypeScript code snippet correctly defines a node for a singly linked list used in this problem?

easy

A. class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val ?? 0; this.next = next ?? null; } }

B. interface ListNode { value: string; next: ListNode; }

C. type ListNode = { val: string; next: ListNode | undefined; };

D. function ListNode(val) { this.val = val; this.next = null; }

Solution

1. Step 1: Check for correct TypeScript class syntax

   class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val ?? 0; this.next = next ?? null; } } defines a class with val as number and next as ListNode or null, with a constructor and default values.

2. Step 2: Verify other options

   interface ListNode { value: string; next: ListNode; } uses interface with string type and no null for next, type ListNode = { val: string; next: ListNode | undefined; }; uses string val and next possibly undefined, function ListNode(val) { this.val = val; this.next = null; } is JavaScript function style without types.

3. Final Answer:

   TypeScript class with number val and nullable next -> Option A

4. Quick Check:

   TypeScript class with number val and nullable next = class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val ?? 0; this.next = next ?? null; } } [OK]

Hint: Use class with val:number and next: ListNode|null [OK]

Common Mistakes:

• Using string instead of number for val
• Not allowing next to be null
• Using JavaScript function instead of TypeScript class

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) Use the standard addition method for linked lists.

medium

A. 7 -> 10 -> 7 -> null

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

C. 7 -> 0 -> 8 -> null

D. 2 -> 0 -> 8 -> null

Solution

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

   2+5=7 (no carry), 4+6=10 (carry 1), 3+4+1=8 (no carry)

2. Step 2: Form the resulting linked list

   Digits are 7, 0 (from 10), and 8, so linked list is 7 -> 0 -> 8 -> null

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option C

4. Quick Check:

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

Hint: Add digits with carry, store remainder in node [OK]

Common Mistakes:

• Not carrying over when sum >= 10
• Reversing the order of digits in output
• Adding digits incorrectly without carry

4. Given this TypeScript function to add two numbers as linked lists, what is the bug?

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  let dummy = new ListNode(0);
  let current = dummy;
  let carry = 0;
  while (l1 !== null && l2 !== null) {
    let sum = l1.val + l2.val + carry;
    carry = Math.floor(sum / 10);
    current.next = new ListNode(sum % 10);
    current = current.next;
    l1 = l1.next;
    l2 = l2.next;
  }
  return dummy.next;
}

medium

A. Carry is not calculated correctly using Math.floor.

B. The function returns dummy instead of dummy.next.

C. Dummy node is not initialized properly.

D. The loop stops when either list ends, missing remaining nodes in longer list.

Solution

1. Step 1: Analyze the while loop condition

   The loop runs only while both l1 and l2 are not null, so it stops if one list is longer.

2. Step 2: Identify missing handling of remaining nodes

   After the loop, remaining nodes of the longer list and any carry are not processed, causing incorrect result.

3. Final Answer:

   Loop stops too early, missing remaining nodes in longer list -> Option D

4. Quick Check:

   Loop condition && misses longer list nodes [OK]

Hint: Use || in loop to handle different length lists [OK]

Common Mistakes:

• Using && instead of || in loop condition
• Not processing leftover carry after loop
• Returning dummy instead of dummy.next

5. You have two linked lists representing numbers: List 1: 9 -> 9 -> 9 -> 9 -> null (9999) and List 2: 1 -> null (1). What is the correct resulting linked list after adding them?

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 -> 10 -> null

Solution

1. Step 1: Add digits with carry from right to left

   9+1=10 (0 carry 1), next 9+0+1=10 (0 carry 1), repeat for next two 9s with carry 1.

2. Step 2: Add final carry as new node

   After last 9+0+1=10, carry 1 remains, so add new node with 1 at the end.

3. Final Answer:

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

4. Quick Check:

   9999 + 1 = 10000 as linked list 0->0->0->0->1 [OK]

Hint: Add carry after last node if needed [OK]

Common Mistakes:

• Not adding extra node for final carry
• Stopping addition early when one list ends
• Incorrectly placing carry node position