Add Two Numbers Represented as Linked List in DSA Javascript - 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, meaning the first node is the ones place. The goal is to add these two numbers and return the sum as a new linked list in the same reversed format. This helps us work with very large numbers that can't fit in normal variables.

Why it matters

Without this method, computers would struggle to add very large numbers that exceed normal limits. Using linked lists to represent numbers allows us to handle numbers of any size, digit by digit, just like how we add numbers by hand. This is important in fields like cryptography, big data, and anywhere large numbers are common.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After this, you can learn about more complex linked list problems like multiplication or subtraction of numbers represented as linked lists, or explore other data structures for big number operations.

Mental Model

Core Idea

Adding two numbers stored as linked lists is like adding digits one by one from right to left, carrying over extra values just like manual addition.

Think of it like...

Imagine adding two long strings of beads where each bead is a digit. You start from the rightmost bead on both strings, add them, and if the sum is more than 9, you carry over a bead to the next position on the left.

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

Add digits:
2 + 5 = 7 (no carry)
4 + 6 = 10 (carry 1)
3 + 4 + 1 = 8 (no carry)

Result: 7 -> 0 -> 8 -> null (represents 807)

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list node is and how nodes connect to form a list.

A linked list is a chain of nodes. Each node has two parts: a value (here, a digit) and a pointer to the next node. The last node points to null, meaning the end of the list. For example, a list 2 -> 4 -> 3 means the first node holds 2, points to the node with 4, which points to the node with 3, which points to null.

Result

You can represent numbers as linked lists where each node holds one digit.

Understanding the linked list structure is essential because the addition process depends on moving through nodes one by one.

2

Foundation

Representing Numbers as Linked Lists

Concept: Numbers are stored in reverse order in linked lists, with each node holding one digit.

For example, the number 342 is stored as 2 -> 4 -> 3 -> null. This reverse order makes addition easier because we start adding from the ones place, which is the head of the list. This setup mimics how we add numbers by hand, starting from the rightmost digit.

Result

You can visualize and store any number as a linked list in reverse order.

Storing digits in reverse order aligns the list traversal with the natural addition order, simplifying the algorithm.

3

Intermediate

Adding Two Digits with Carry

🤔Before reading on: When adding two digits plus a carry, do you think the carry applies before or after summing the digits? Commit to your answer.

Concept: When adding digits from two nodes, include any carry from the previous addition before deciding the new carry.

Add the two digits and the carry from the previous step. If the sum is 10 or more, subtract 10 and carry 1 to the next addition. For example, 7 + 8 + 1 (carry) = 16, so store 6 and carry 1.

Result

You can correctly add digits with carry, just like manual addition.

Including the carry in each addition step ensures the sum is accurate and mimics real-world addition.

4

Intermediate

Traversing Both Lists Simultaneously

🤔Before reading on: If one list is longer than the other, do you think you should stop when the shorter ends or continue? Commit to your answer.

Concept: Traverse both linked lists node by node, adding corresponding digits and carry, continuing until both lists and carry are fully processed.

Start from the heads of both lists. Add their digits and carry. Move to the next nodes in both lists. If one list ends, treat its digit as 0. Continue until both lists are done and no carry remains.

Result

You can handle lists of different lengths and still add correctly.

Continuing until both lists and carry are done ensures no digits or carry are missed, handling uneven list lengths gracefully.

5

Intermediate

Building the Result Linked List

Concept: Create a new linked list to store the sum digits as you add them.

For each sum digit, create a new node and link it to the result list. Keep track of the last node to append new nodes easily. At the end, the result list represents the sum in reverse order.

Result

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

Building the result list on the fly lets you return the sum in the same format as inputs, ready for further use.

6

Advanced

Complete JavaScript Implementation

🤔Before reading on: Do you think the code should handle carry after the last nodes? Commit to your answer.

Concept: Combine all steps into a working JavaScript function that adds two numbers represented as linked lists.

```javascript class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function addTwoNumbers(l1, l2) { 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; } // Example usage: // Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) // Output: 7 -> 0 -> 8 // Create lists let l1 = new ListNode(2, new ListNode(4, new ListNode(3))); let l2 = new ListNode(5, new ListNode(6, new ListNode(4))); let result = addTwoNumbers(l1, l2); // Print result let output = []; while (result) { output.push(result.val); result = result.next; } console.log(output.join(' -> ') + ' -> null'); ```

Result

7 -> 0 -> 8 -> null

Handling carry after the last nodes and using a dummy head simplifies code and prevents edge case bugs.

7

Expert

Handling Edge Cases and Optimization

🤔Before reading on: Do you think the algorithm changes if digits are stored in forward order? Commit to your answer.

Concept: Understand how to handle cases like empty lists, very long lists, and how the approach differs if digits are stored forward.

If one or both lists are empty, treat missing nodes as zero. For very long lists, the algorithm still works because it processes node by node. If digits are stored forward (most significant digit first), you must reverse the lists first or use recursion to add from the end. This adds complexity and changes the approach.

Result

You can handle all input variations and know when to adapt the algorithm.

Knowing how storage order affects the algorithm prepares you for variations and real-world data inconsistencies.

Under the Hood

Internally, the algorithm iterates through both linked lists simultaneously, adding corresponding digits and a carry value. It uses a dummy head node to simplify list construction. Each sum digit is stored in a new node. Carry is calculated by dividing the sum by 10, and the remainder is stored as the node's value. This process continues until all nodes and carry are processed, ensuring the sum is correct digit by digit.

Why designed this way?

This design mimics manual addition, which is intuitive and efficient. Using a dummy head avoids special cases for the first node. Processing digits in reverse order aligns with natural addition from least significant digit to most. Alternatives like converting lists to numbers fail for very large inputs due to overflow, so this node-by-node approach is scalable and safe.

┌─────────────┐      ┌─────────────┐      ┌─────────────┐
│ List1 Node  │      │ List2 Node  │      │ Result Node │
│  val = d1   │      │  val = d2   │      │  val = sum  │
└─────┬───────┘      └─────┬───────┘      └─────┬───────┘
      │                    │                    │
      │                    │                    │
      ▼                    ▼                    ▼
  Next Node            Next Node            Next Result
      │                    │                    │
      ▼                    ▼                    ▼
  ... continues ...     ... continues ...     ... continues ...

Carry flows between additions, influencing sum calculation at each step.

Myth Busters - 4 Common Misconceptions

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

Common Belief: Some think adding two numbers as linked lists means joining the lists end to end.

Reality: You must add corresponding digits with carry, not just join lists. Concatenation does not perform addition.

Why it matters: Concatenating lists instead of adding digits leads to incorrect results and breaks the logic of number addition.

Quick: Do you think the carry can be ignored if the sum digit is less than 10? Commit to yes or no.

Common Belief: People often believe carry is only needed when sum is exactly 10.

Reality: Carry is needed whenever sum is 10 or more, not just exactly 10.

Why it matters: Ignoring carry when sum is greater than 10 causes wrong digits in the result, leading to incorrect sums.

Quick: Do you think the algorithm works the same if digits are stored in forward order? Commit to yes or no.

Common Belief: Many assume the same addition method works regardless of digit order in the list.

Reality: If digits are stored forward, you must reverse the lists or use recursion to add from the end, as addition starts from least significant digit.

Why it matters: Using the wrong approach for forward order digits causes incorrect sums and complicates the algorithm.

Quick: Do you think the result list can be built by modifying one of the input lists? Commit to yes or no.

Common Belief: Some believe you can reuse and modify input lists to save space.

Reality: Modifying input lists can cause side effects and bugs; creating a new list is safer and clearer.

Why it matters: Reusing input lists can lead to unexpected behavior if those lists are used elsewhere, causing hard-to-find bugs.

Expert Zone

1

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

2

Carry must be handled after processing all nodes to avoid missing an extra digit in the result.

3

Reversing lists for forward order digits is a common technique but adds overhead; recursion can be an elegant alternative.

When NOT to use

This approach is not suitable if digits are stored in forward order without reversal or recursion. For extremely large numbers where performance is critical, specialized big integer libraries or arrays might be better. Also, if memory is very limited, in-place modification might be considered but with caution.

Production Patterns

In production, this pattern is used in big number arithmetic libraries, blockchain transaction processing, and cryptography where numbers exceed standard data types. Developers often combine this with other linked list operations and optimize memory usage by pooling nodes.

Connections

Big Integer Arithmetic

Builds-on

Understanding linked list addition helps grasp how big integer libraries perform arithmetic on numbers larger than built-in types.

Manual Addition Algorithm

Same pattern

The linked list addition algorithm directly models how humans add numbers digit by digit, showing how computer algorithms mimic human logic.

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 principles.

Common Pitfalls

#1 Stopping addition when the shorter list ends, ignoring remaining digits and carry.

Wrong approach:

while (l1 !== null && l2 !== null) {
// add digits
}
// no further processing

Correct approach:

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

Root cause:

Misunderstanding that addition must continue until all digits and carry are processed.

#2 Not handling carry after the last nodes, missing an extra digit in the result.

Wrong approach:

while (l1 !== null || l2 !== null) {
// add digits
}
// no carry check after loop

Correct approach:

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

Root cause:

Assuming carry is only relevant inside the loop and forgetting it can create a new digit.

#3 Modifying input lists directly to store result digits.

Wrong approach:

l1.val = sum % 10;
l1 = l1.next;
l2 = l2.next;

Correct approach:

Create new nodes for result list without changing l1 or l2.

Root cause:

Trying to save memory but risking side effects and bugs by altering inputs.

Key Takeaways

Adding two numbers as linked lists involves digit-by-digit addition with carry, mimicking manual addition.

Digits are stored in reverse order to align list traversal with addition order, simplifying the algorithm.

A dummy head node simplifies building the result list and avoids special cases for the first node.

Carry must be handled carefully at every step, including after processing all nodes, to ensure correct sums.

Handling edge cases like different list lengths and empty lists is essential for a robust solution.

Practice

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

easy

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

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

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

D. Find the difference between two numbers represented as linked lists.

Solution

1. Step 1: Understand the problem statement

   The problem requires adding two numbers where each number is represented by a linked list. Each node contains a single digit, and digits are stored in reverse order.

2. Step 2: Identify the expected output

   The output should be a linked list representing the sum of the two numbers, also in reverse order.

3. Final Answer:

   Add two numbers represented as linked lists and return their sum as a linked list -> Option A

4. Quick Check:

   Adding digits node by node = Add linked lists [OK]

Hint: Remember digits are reversed in linked lists [OK]

Common Mistakes:

• Thinking digits are stored in normal order
• Confusing addition with multiplication
• Returning a number instead of a linked list

2. Which of the following is the correct way to create a node for a singly linked list in JavaScript for this problem?

easy

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

B. class ListNode { constructor(val) { this.value = val; this.nextNode = null; } }

C. let node = { value: val, next: null };

D. function Node(val) { this.val = val; this.nextNode = null; }

Solution

1. Step 1: Check the standard node structure

   The node should have a property named 'val' for the digit and 'next' for the next node pointer.

2. Step 2: Verify the syntax correctness

   function ListNode(val) { this.val = val; this.next = null; } correctly defines a function constructor with 'val' and 'next' properties initialized properly.

3. Final Answer:

   function ListNode(val) { this.val = val; this.next = null; } -> Option A

4. Quick Check:

   Node with val and next properties = function ListNode(val) { this.val = val; this.next = null; } [OK]

Hint: Use 'val' and 'next' for node properties [OK]

Common Mistakes:

• Using 'value' instead of 'val'
• Using 'nextNode' instead of 'next'
• Incorrect constructor syntax

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)

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

medium

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

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

C. 7 -> 1 -> 7 -> null

D. 8 -> 0 -> 7 -> null

Solution

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

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

2. Step 2: Form the resulting linked list

   The digits are 7 -> 0 -> 8 representing 807 in reverse order.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Ignoring carry after adding digits
• Mixing digit order in output
• Returning sum as a number, not linked list

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

function addTwoNumbers(l1, l2) {
  let dummy = new ListNode(0);
  let current = dummy;
  let carry = 0;
  while (l1 !== null && l2 !== null) {
    let sum = carry + l1.val + l2.val;
    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. The function does not return the dummy node itself.

B. The carry is not calculated correctly using Math.floor.

C. The dummy node should be initialized with value 1 instead of 0.

D. The loop condition should use '||' instead of '&&' to handle lists of different lengths.

Solution

1. Step 1: Analyze the loop condition

   The loop stops when either l1 or l2 becomes null, missing remaining nodes if lists differ in length.

2. Step 2: Correct the loop condition

   Using '||' ensures the loop continues until both lists and carry are fully processed.

3. Final Answer:

   The loop condition should use '||' instead of '&&' to handle lists of different lengths. -> Option D

4. Quick Check:

   Loop condition must cover all nodes = The loop condition should use '||' instead of '&&' to handle lists of different lengths. [OK]

Hint: Use '||' to continue while any list or carry remains [OK]

Common Mistakes:

• Stopping loop too early with '&&'
• Ignoring leftover carry after loop
• Not advancing pointers correctly

5. Given two linked lists representing numbers in reverse order, how would you modify the addition function to handle the case where the input lists have different lengths and the final carry creates a new node? Choose the best approach to ensure correct output for inputs like: List 1: 9 -> 9 -> 9 -> null (represents 999) List 2: 1 -> null (represents 1)

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

hard

A. Add zeros to the shorter list before starting the addition to equalize lengths.

B. Stop the loop when both lists end and ignore carry since it won't affect the sum.

C. Use a loop condition that continues while l1, l2, or carry exists, adding carry as a new node if needed.

D. Only add nodes while both lists have nodes, then append the remaining nodes without addition.

Solution

1. Step 1: Understand the need to handle different lengths and carry

   When lists differ in length, addition must continue until both lists and carry are fully processed.

2. Step 2: Use a loop condition that checks l1, l2, or carry

   This ensures the loop adds all digits and creates a new node if carry remains after lists end.

3. Final Answer:

   Use a loop condition that continues while l1, l2, or carry exists, adding carry as a new node if needed. -> Option C

4. Quick Check:

   Loop until all digits and carry processed = Use a loop condition that continues while l1, l2, or carry exists, adding carry as a new node if needed. [OK]

Hint: Loop while any list or carry remains to add all digits [OK]

Common Mistakes:

• Ignoring carry after lists end
• Trying to pad shorter list manually
• Appending leftover nodes without adding carry