2. Add Two Numbers

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// ListNode definition directly from leetcode
let ListNode = function(val) {
  this.val = val;
  this.next = null;
};

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

let addTwoNumbers = function(l1, l2) {
  let carry = 0;
  let sum = 0;
  let pointer1 = l1;
  let pointer2 = l2;
  let pointer = l1;

  let lsum = null;
  let lsumPointer = null;

  while (!(pointer === null && carry === 0)) {
    if (pointer1 && pointer2 != null) {
      sum = pointer1.val + pointer2.val;
    } else {
      //if one number is longer than the other
      //one pointer is going to be null while
      //the other is still pointing to the longer number
      if (pointer1 != null) {
        sum = pointer1.val;
      } else if (pointer2 != null) {
        sum = pointer2.val;
      } else {
        sum = 0; //both pointers are null, we're just adding the carry from last sum
      }
    }

    sum += carry === 1 ? 1 : 0;

    carry = sum >= 10 ? 1 : 0;

    //single digit sum
    sum = sum % 10;

    let node = new ListNode(sum);

    //initial run through needs to set up the sum linked list
    if (lsum === null) {
      lsum = node;
      lsumPointer = lsum;
    } else {
      //have the current sum node point to the new node
      lsumPointer.next = node;

      //point to the new node
      lsumPointer = node;
    }

    pointer1 = pointer1 != null ? pointer1.next : null;
    pointer2 = pointer2 != null ? pointer2.next : null;
    pointer = pointer1 === null ? pointer2 : pointer1;
  }

  return lsum;
};

Analysis

Since the digits are stored in reverse order, the algorithm is basically the same exact one you use to add two numbers in real life. My solution involves three pointers, one for each linked list and then an additional one pointing to whichever linked list is currently being traversed since there is no gaurentee that both linked lists are the same length. We iterate over each integer in the lists and keep track of the carry digit as we go.

This problem wasn't exactly difficult but it was deceptively complicated. You'd expect it to be really easy because it's just basic operations with linked lists and grade school arirthmetic. The hardest part was making sure to carry through the carry digit when you reached the final digits of the lists, like for 99+1 and you end up with a three digit number. At that point, both pointers will be null so we end up needing to check for that during every single iteration.

Anyway we iterate over each list only once, the running time will just be O(l1.length, l2.length). Since we never make any dummy nodes, the space complexity is the same.