Add Two Numbers Represented as Linked List in DSA Typescript - Deep Dive

Overview - Add Two Numbers Represented as Linked List

What is it?

This topic is about adding two numbers where each number is stored as a linked list. Each node in the list holds a single digit, and the digits are stored in reverse order. The goal is to add these two numbers and return the sum as a linked list in the same reversed format. This helps us work with very large numbers that normal variables cannot hold.

Why it matters

Without this method, computers would struggle to add very large numbers that exceed their normal storage limits. Using linked lists to represent numbers allows us to handle numbers of any size, digit by digit. This is important in fields like cryptography, big data, and scientific computing where huge numbers are common.

Where it fits

Before this, you should understand what linked lists are and how to traverse them. After this, you can learn about other linked list operations like subtraction, multiplication, or more complex data structures like trees and graphs.

Mental Model

Core Idea

Adding two numbers digit by digit, carrying over extra value, just like how you add numbers by hand, but using linked lists to hold each digit.

Think of it like...

Imagine adding two long strings of beads where each bead shows a digit. You add bead by bead from right to left, carrying over if the sum is more than 9, just like adding numbers on paper.

  List1: 2 -> 4 -> 3 -> null
+ List2: 5 -> 6 -> 4 -> null
-------------------------
  Sum : 7 -> 0 -> 8 -> null

Explanation:
  342 + 465 = 807
  Stored reversed as linked list digits.

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Digit Storage

Concept: Learn how numbers are stored in linked lists with each node holding one digit in reverse order.

A linked list stores digits of a number in reverse order. For example, the number 123 is stored as 3 -> 2 -> 1 -> null. This means the head node holds the least significant digit (ones place). This makes addition easier because we start adding from the head node.

Result

You can represent any number as a linked list where each node is a digit, starting from the smallest place value.

Understanding this storage method is key because it aligns with how addition naturally proceeds from right to left.

2

Foundation

Traversing Linked Lists Node by Node

Concept: Learn how to move through linked lists one node at a time to access digits.

To add two numbers, you need to visit each node in both linked lists. You start at the head of each list and move to the next node until you reach the end (null). This lets you access each digit in order.

Result

You can access each digit of the numbers stored in linked lists sequentially.

Knowing how to traverse linked lists is essential to process each digit for addition.

3

Intermediate

Adding Digits with Carry Handling

🤔Before reading on: do you think adding digits without carry will always give the correct sum? Commit to yes or no.

Concept: Introduce the idea of carrying over when the sum of two digits exceeds 9.

When adding two digits, if their sum is 10 or more, you keep the last digit and carry over 1 to the next addition. For example, 7 + 8 = 15, so you store 5 and carry 1 to add to the next digits.

Result

You can correctly add digits and handle cases where sums exceed 9 by carrying over.

Handling carry is crucial because it mimics real addition and ensures the sum is accurate across all digits.

4

Intermediate

Handling Different Length Lists

🤔Before reading on: do you think two linked lists of different lengths can be added without extra steps? Commit to yes or no.

Concept: Learn how to add numbers when linked lists have different lengths by treating missing digits as zero.

If one list is shorter, treat missing nodes as zero during addition. For example, adding 342 (3 nodes) and 45 (2 nodes) means adding 2 -> 4 -> 3 and 5 -> 4 -> 0. This keeps addition consistent.

Result

You can add numbers of different lengths without errors.

Treating missing digits as zero prevents errors and simplifies addition logic.

5

Intermediate

Creating the Result Linked List

Concept: Learn how to build a new linked list to store the sum digit by digit.

As you add digits and handle carry, create new nodes for each sum digit and link them together. This new list represents the sum in reverse order, just like the inputs.

Result

You get a new linked list representing the sum of the two numbers.

Building the result list on the fly keeps memory usage efficient and matches the input format.

6

Advanced

Implementing the Full Addition Algorithm

🤔Before reading on: do you think the carry after the last digits can be ignored? Commit to yes or no.

Concept: Combine traversal, addition, carry, and list creation into one complete algorithm.

Start with carry = 0. While either list has nodes or carry is not zero: - Add current digits and carry. - Create a new node with sum % 10. - Update carry to Math.floor(sum / 10). - Move to next nodes. Return the head of the new list. Example code in TypeScript: class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val === undefined ? 0 : val; this.next = next === undefined ? null : next; } } function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null { let dummyHead = new ListNode(0); let current = dummyHead; let carry = 0; while (l1 !== null || l2 !== null || carry !== 0) { let val1 = l1 ? l1.val : 0; let val2 = l2 ? l2.val : 0; let sum = val1 + val2 + carry; carry = Math.floor(sum / 10); current.next = new ListNode(sum % 10); current = current.next; if (l1) l1 = l1.next; if (l2) l2 = l2.next; } return dummyHead.next; }

Result

The function returns a linked list representing the sum of the two input numbers.

Combining all parts into one loop simplifies the code and ensures all cases, including leftover carry, are handled.

7

Expert

Optimizing and Edge Case Handling

🤔Before reading on: do you think the algorithm works correctly if both inputs are null? Commit to yes or no.

Concept: Learn about edge cases like empty lists, very large numbers, and optimizing memory usage.

Edge cases include: - Both lists null: return a node with 0 to represent zero. - One list null: return the other list. - Very large numbers: algorithm handles any length. Optimization: - Use a dummy head to simplify list creation. - Avoid unnecessary node creation. - Carefully handle carry after last digit. This ensures robustness in real-world use.

Result

The algorithm correctly handles all edge cases and is efficient.

Anticipating edge cases and optimizing memory makes the solution production-ready and reliable.

Under the Hood

The algorithm works by iterating through both linked lists simultaneously, adding corresponding digits along with any carry from the previous addition. Each sum is split into a digit (sum modulo 10) stored in a new node, and a carry (sum divided by 10) passed to the next addition. This mimics manual addition digit by digit. The use of a dummy head node simplifies the linked list construction by providing a fixed starting point.

Why designed this way?

Storing digits in reverse order aligns with natural addition from least significant digit to most significant. Using linked lists allows handling numbers larger than built-in types. The dummy head pattern avoids special cases for the first node, making code cleaner and less error-prone. Alternatives like storing digits in forward order require reversing lists or recursion, which complicates the algorithm.

┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│ List1 Node  │ --> │ List1 Node  │ --> │ List1 Node  │ --> null
│ (digit) 2   │     │ (digit) 4   │     │ (digit) 3   │
└─────────────┘     └─────────────┘     └─────────────┘

┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│ List2 Node  │ --> │ List2 Node  │ --> │ List2 Node  │ --> null
│ (digit) 5   │     │ (digit) 6   │     │ (digit) 4   │
└─────────────┘     └─────────────┘     └─────────────┘

Iteration steps:
[Add digits + carry] -> [Create new node with sum%10] -> [Update carry]

Result List:
┌─────────────┐ --> ┌─────────────┐ --> ┌─────────────┐ --> null
│ Result Node │     │ Result Node │     │ Result Node │
│ (digit) 7   │     │ (digit) 0   │     │ (digit) 8   │
└─────────────┘     └─────────────┘     └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think you can add two linked lists by just concatenating them? Commit to yes or no.

Common Belief: You can add two numbers by just joining their linked lists end to end.

Reality: Concatenating lists does not add the numbers; it just joins the sequences. You must add digits node by node with carry.

Why it matters: Concatenation leads to wrong results and breaks the logic of digit-wise addition.

Quick: Do you think the carry after the last digit can be ignored? Commit to yes or no.

Common Belief: If the last digit addition produces a carry, it can be ignored because there are no more digits.

Reality: The carry must be added as a new node at the end to represent the correct sum.

Why it matters: Ignoring the final carry causes incorrect sums, especially when the last addition exceeds 9.

Quick: Do you think the order of digits in the linked list doesn't matter for addition? Commit to yes or no.

Common Belief: Digits can be stored in any order and addition will still work the same.

Reality: Digits must be stored in reverse order (least significant digit first) for this addition method to work simply.

Why it matters: Storing digits in forward order requires more complex algorithms like reversing lists or recursion.

Quick: Do you think adding two null linked lists should return null? Commit to yes or no.

Common Belief: Adding two empty lists means no number, so the result should be null.

Reality: Adding two empty lists represents adding zero plus zero, so the result should be a node with digit 0.

Why it matters: Returning null can cause errors in code expecting a valid list representing zero.

Expert Zone

1

The dummy head node pattern simplifies linked list construction and avoids special cases for the first node.

2

Handling carry as a separate variable outside the loop condition ensures no digit is missed, even if carry remains after both lists end.

3

The algorithm naturally supports arbitrarily large numbers limited only by memory, unlike fixed-size integer types.

When NOT to use

This approach is not suitable if digits are stored in forward order; in that case, you need to reverse the lists first or use recursion. Also, for very performance-critical systems, specialized big integer libraries or hardware support might be better.

Production Patterns

In production, this pattern is used in big integer arithmetic libraries, blockchain transaction processing, and any system needing arbitrary precision arithmetic. It is often combined with other data structures for efficiency and extended to support subtraction and multiplication.

Connections

Big Integer Arithmetic

Builds-on

Understanding linked list addition is a foundation for implementing big integer arithmetic where numbers exceed built-in types.

Manual Addition Algorithm

Same pattern

The linked list addition mimics the manual addition process digit by digit, showing how algorithms often reflect human problem-solving.

Carry Propagation in Digital Circuits

Analogous process

Carry handling in linked list addition is similar to carry propagation in digital adders, connecting software algorithms to hardware design.

Common Pitfalls

#1 Ignoring carry after the last digit addition.

Wrong approach:

while (l1 !== null || l2 !== null) {
// add digits and carry
// create node
// update carry
}
// no check for carry after loop

Correct approach:

while (l1 !== null || l2 !== null || carry !== 0) {
// add digits and carry
// create node
// update carry
}

Root cause:

Not including carry in the loop condition causes leftover carry to be lost.

#2 Assuming both lists have the same length and not checking for null nodes.

Wrong approach:

while (l1 !== null && l2 !== null) {
// add digits
// move to next
}

Correct approach:

while (l1 !== null || l2 !== null || carry !== 0) {
// add digits with zero if null
// move to next
}

Root cause:

Using && instead of || misses digits when lists differ in length.

#3 Modifying input lists instead of creating a new result list.

Wrong approach:

l1.val = (l1.val + l2.val + carry) % 10;
// reusing l1 nodes as result

Correct approach:

Create new nodes for the result list without changing inputs.

Root cause:

Mutating inputs can cause side effects and bugs if inputs are used elsewhere.

Key Takeaways

Numbers can be stored as linked lists with digits in reverse order to simplify addition.

Adding two numbers digit by digit with carry mimics manual addition and works well with linked lists.

Handling different lengths and leftover carry ensures the algorithm works for all inputs.

Using a dummy head node simplifies building the result linked list and avoids special cases.

This method supports arbitrarily large numbers and is foundational for big integer arithmetic.

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