Skip to content

2. Add Two Numbers

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

Example 1: 

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2: 
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3: 
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Problem Analysis

Note that the provided linked lists are already reversed so you won't have to reverse them.

Looking at the list items you will have to do a typical math addition for each of the input nodes on the same position while making sure the carry bit is propagated.

For example given l1=[4], l2=[6] then l1+l2 % 10 = 10 % 10 = 0 and carry= 10 / 10 = 1. So we push 0 into the result first and use the carry bit for the next addition.

Once you run out of items in l1 and l2 you do one final check for the carry bit and add 1 to the result.

Solutions

There is only one technique here. We first create a result LinkedList node and a current LinkedList node that points to the current item on the list on each step of the addition.

We check whether we run out of l1, l2 items and add each item on the list one by one.

The following program shows how to implement this approach:

Solution
AddTwoNumbers.js
/**
 * Definition for singly-linked list.
 * 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, l2) {
  // We need this node to return the pointer to the first element of the list
  const res = new ListNode();
  let carry = 0;
  let curr = res;
  // While we have elements in both lists
  while (l1 || l2) {
    if (l1) {
      carry += l1.val;
      l1 = l1.next;
    }
    if (l2) {
      carry += l2.val;
      l2 = l2.next;
    }
    // next_digit=a+b%10
    curr.next = new ListNode(carry % 10);
    curr = curr.next;
    // carry=a+b//10
    carry = Math.floor(carry / 10);
  }

  // Check one last time the carry bit
  if (carry > 0) {
    curr.next = new ListNode(carry);
    curr = curr.next;
  }

  return res.next;
}

Complexity is O(n) When n the length of the largest list. O(m + n) Space. A temporary linked list is needed to store the output number.

Additional Thoughts

What if the provided linked lists are not reversed?

You will have to reverse the input lists first, better doing that on a new list without modifying the existing input ones. Problem 206. Reverse Linked List deals with this case.

  • Understand how to iterate over a Linked List a HashTable.

References