loading...
Cover image for Add Two Numbers Problems: How to Sum Two Linked Lists

Add Two Numbers Problems: How to Sum Two Linked Lists

alisabaj profile image Alisa Bajramovic Updated on ・6 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Hey! Today's algorithm is one of the most popular ones on Leetcode: adding 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 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.

So, let's say you were given two linked lists: 2 > 4 > 3 and 5 > 6 > 4. To add those numbers, you'd do the reverse of both of them: 342 + 465, which equals 807. Therefore, the output of this problem should be 7 > 0 > 8.

I think one of the trickiest parts of this problem is the issue of the carried number -- if every pair of nodes added to a number less than 10, then there wouldn't be a concern of 'carrying' digits over to the next node. However, as you can see in the example above, adding numbers like 4 and 6 produces a carry, which you have to account for when adding 3 and 4.

In this post, I'll first draw a diagram of how I'm going to approach this problem. Then, in JavaScript, I'll walkthrough my code of the solution.

Approaching The Problem

First, I'll start with two linked lists 1 > 6 > 4 and 2 > 6 > 3. I know the solution I want is another linked list whose value is 3 > 2 > 8. The reason I know that's the solution is that 463 + 362 = 823, and when backwards and put into a linked list, that number is 3 > 2 > 8.

Two linked lists: `1 > 6 > 4` and `2 > 6 > 3`. Beneath them is the solution we're going for, `3 > 2 > 8`

Now, I'll start by getting the value of the first node of both linked lists. 1 + 2 = 3. Since 3 is smaller than 10, no number needs to be carried over, so I'll just put 3 into a new node.

The first nodes of both linked lists are circled and then added. 1 + 2 = 3, which is a single digit number, so it can go into a new node right away.

Now I'll move onto the next node in both list. 6 + 6 = 12. Since 12 is not a single digit number, the 1 will be carried over to the next round, and the 2 will be put into a node for the solution.

The second nodes of both linked lists are circled and then added. 6 + 6 = 12, which is a double digit number, so the 2 can go into a node, but the 1 has to be carried over.

Next are 4 and 3. 4 + 3 = 7, plus there's the carried over 1 from the previous round. 7 + 1 = 8, and since 8 is a single digit number, we can put it into a new node in the solution.

The third nodes of both linked lists are circled and then added. 4 + 3 = 7, and we have to add 1 which was carried over from the previous round, so the total is 8. 8 is single digit, so we can put it into a new node for the solution.

Since there are no more nodes to check in either linked list, we have our solution: 3 > 2 > 8.

Coding the Solution

The Leetcode problem gives us a function for a singly-linked list, which has the properties of 'value' and 'next' (next points to the next node in the list).

The first thing I'll do in this problem is create a new list, and set a new variable currentNode equal to the list. This list is what will be returned at the end of the problem. Because in the function we'll want to return each node of the list, we can add a return statement at the bottom, using .next.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  //...

  return list.next;
}

Now, we'll initiate two variables, sum and carry. Sum will hold the value of adding the nodes, and carry will hold any number that'll need to be carried over to the next node. We can start by setting both of these values to 0.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  let sum = 0;
  let carry = 0;

  //...

  return list.next;
}

Next, we'll need to create a while loop, which will check the nodes and their values until there are no nodes left to check. If one list is longer than the other, we still will want to add the longer list's nodes to the solution, so we'll have to make sure we continue to check so long as the nodes aren't null. That means the while loop should keep going as long as list 1 isn't null OR list 2 isn't null.

But, there's one more case we have to account for: what if we're done checking both nodes, but there's still a 'carried' value. For example, if the given lists were 5 and 5, then the output should be 0 > 1. Since a number is being carried over, we'll need to enter the while loop again. That means that as long as there's a leftover sum, or sum > 0, or either of the lists still have nodes to be checked, we'll keep going through the while loop.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  let sum = 0;
  let carry = 0;

  while (l1 !== null || l2 !== null || sum > 0) {
    //...
  }

  return list.next;
}

Now we're in the while loop. We'll want to add values to the sum if there are still values to add, so we'll have two very similar if-statements. If a node still has value, then we'll add that value to the sum. We'll then move onto the next node in the list. We'll do the same for both l1 and l2.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  let sum = 0;
  let carry = 0;

  while (l1 !== null || l2 !== null || sum > 0) {
    if (l1 !== null) {
      sum += l1.val;
      l1 = l1.next;
    }

    if (l2 !== null) {
      sum += l2.val;
      l2 = l2.next;
    }

    //...
  }

  return list.next;
}

Now is the point we have to deal with the possibility of a carried over number. If sum is greater than or equal to 10, then there will be a carry. There's a few ways to check for this, but I like to use division and modulo.

If sum = 13, then we know the carry should be 1. To get the carry, we can divide the sum by 10. Since we don't want a remainder, we can use Math.floor(). Math.floor(13/10) is 1, which is the carry that we want.

For the sum, we just want what's in the ones-digit spot of 13 (aka we just want 3). We'll only be adding 3 to the result. To single out this digit, we can use modulo. 13 % 10 gives us 3, because the remainder of 13/10 is 3.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  let sum = 0;
  let carry = 0;

  while (l1 !== null || l2 !== null || sum > 0) {
    if (l1 !== null) {
      sum += l1.val;
      l1 = l1.next;
    }

    if (l2 !== null) {
      sum += l2.val;
      l2 = l2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    //...
  }

  return list.next;
}

Now, we'll want to add a new node to our solution list, and give it the value of the sum. We'll also want to move over in our list, and reset the currentNode to equal the next node we've just added.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  let sum = 0;
  let carry = 0;

  while (l1 !== null || l2 !== null || sum > 0) {
    if (l1 !== null) {
      sum += l1.val;
      l1 = l1.next;
    }

    if (l2 !== null) {
      sum += l2.val;
      l2 = l2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    currentNode.next = new ListNode(sum);
    currentNode = currentNode.next;

    //...
  }

  return list.next;
}

Finally, the last thing we'll want to do is move any carry value to sum, setting carry back equal to 0. This way, when the cycle repeats for the next node, the sum will start with any value that was carried over. And, given that our while-loop has a conditional for if sum > 0, if there's a number that's being carried over, then a new node will be made.

function addTwoNumbers(l1, l2) {
  let list = new ListNode(0);
  let currentNode = list;

  let sum = 0;
  let carry = 0;

  while (l1 !== null || l2 !== null || sum > 0) {
    if (l1 !== null) {
      sum += l1.val;
      l1 = l1.next;
    }

    if (l2 !== null) {
      sum += l2.val;
      l2 = l2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    currentNode.next = new ListNode(sum);
    currentNode = currentNode.next;

    sum = carry;
    carry = 0;
  }

  return list.next;
}

--

Please let me know in the comments if you have any questions or alternate approaches to this problem!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

Code / concept is very clear.
However, it does not make sense why you have sum > 0 in your while loop at first, all the way until you introduce sum = carry.