Add Two Numbers LeetCode Solution

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.

Example:

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

Understand The Problem

The first step in problem-solving is to understand the problem.

When you read the problem statement, you might immediately have ideas on how to solve it. Do not jump to conclusions and do not let your mind fool you. It’s best not to trust your instincts, and instead, you should go through systematic steps of analyzing the problem. Using a system will dramatically reduce the chance of a mistake.

Note: During the interview, make sure to ask questions before you start solving the problem! Interviewers often give a vague problem definition, and you have to fill in the details by asking questions.

Let’s look at the problem statement:

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

There is a lot to unpack in every problem statement. First, let’s look at the question overall and then highlight the key parts:

• Two non-empty linked lists are given.
• Each linked list represents a non-negative integer.
• The digits in each linked list are stored in reverse order.
• Each node in the linked list contains a single digit.
• We need to add the two numbers represented by the linked lists.
• We return the sum as a linked list.

From this information, we can form a basic idea of how the function will look like:

public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Your code here
    }
}

At this point, we have no idea how to solve anything. However, we do know the input, we do know the output, and we have a basic sense of the algorithm. Let’s dive a little more into the details before we try coming up with a solution…

Let’s analyze the input.

• Linked Lists (l1 and l2):
  • Could the linked lists be empty?
    • No, they are non-empty.
  • Can we expect the linked lists to have the same length?
    • No, they can have different lengths.
  • Could the linked lists contain cycles?
    • No, they are non-cyclic.
  • Could the linked lists contain duplicate values?
    • Yes, but each value represents a single digit.

Note: Notice how simple these questions are. Yet they are so crucial. ANY change in the answers can mean the difference between solving the algorithm and getting it wrong.

Then, analyze the digits:

• Digits in Linked Lists:
  • Are the digits stored in reverse order?
    • Yes.
  • Are there any constraints on the digits?
    • No, they can be any non-negative integer.

We now have a basic understanding of the problem. Let’s try to come up with a solution.

Note: There’s always a chance you miss something – even after carefully examining each detail. Don’t worry. It’s natural. However, you should treat every mistake as an opportunity to improve. Why did you make a mistake? Can you improve your problem-solving system to ensure that you don’t make the same mistake again? That’s the whole point of learning: identify weaknesses, improve your system, and repeat. Iterate, iterate, iterate.

Coming Up With The Solution

Each algorithm problem is different. There is no single approach that will help you solve every problem. However, I recommend starting by creating examples and walking through them.

Let’s start by creating examples:

• Example 1
  • l1 = 2 -> 4 -> 3
  • l2 = 5 -> 6 -> 4
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where both linked lists have the same length.
• Example 2
  • l1 = 1 -> 8
  • l2 = 0
  • Why this example?
    • This input is nice because it tests the scenario where one linked list is longer than the other.
    • It also tests the scenario where one linked list is shorter than the other.
• Example 3
  • l1 = 5 -> 9 -> 9
  • l2 = 5
  • Why this example?
    • This input is nice because it tests the scenario where the sum of two numbers results in a carry.
    • It also tests the scenario where the resulting sum has more digits than either of the input numbers.

Note: The number of examples you can go through during the interview will be limited. If you have infinite time, it’s best to try a lot of examples where each examines a specific edge-case. However, you don’t have infinite time in an interview, so you have to strike the balance between speed and accuracy.

As a result of not having a lot of time, let’s pick an example that seems to cover various edge-cases:

• l1 = 2 -> 4 -> 3
• l2 = 5 -> 6 -> 4

This example is nice because:

• It’s a simple case with two linked lists of equal length.
• It involves carrying over to the next digit.
• It produces a sum with more digits than either input number.

Exercise:

With the observations in mind, let’s take the example l1 = 2 -> 4 -> 3 and l2 = 5 -> 6 -> 4 and start thinking about how we can add the two numbers:

• We need to iterate through both linked lists simultaneously:
  • We’ll start from the head of both linked lists.
  • At each step, we’ll add the corresponding digits from both linked lists along with any carry from the previous step.
  • We’ll calculate the sum and the carry and update the result linked list accordingly.
  • If one linked list is shorter than the other, we’ll assume its remaining digits are 0.

Example Dry Run:

• Let’s say our linked lists are l1 = 2 -> 4 -> 3 and l2 = 5 -> 6 -> 4.
• We’ll start from the head of both linked lists (l1 and l2).
• At the first step, we’ll add the digits 2 and 5 along with any carry from the previous step (which is initially 0).
  • Sum: 2 + 5 + 0 = 7
  • Result linked list: 7
  • Carry: 0
• At the second step, we’ll add the digits 4 and 6 along with the carry from the previous step (which is 0).
  • Sum: 4 + 6 + 0 = 10
  • Result linked list: 7 -> 0
  • Carry: 1
• At the third step, we’ll add the digits 3 and 4 along with the carry from the previous step (which is 1).
  • Sum: 3 + 4 + 1 = 8
  • Result linked list: 7 -> 0 -> 8
  • Carry: 0
• Since we have reached the end of both linked lists, we have completed the addition.

From this exercise, we have derived an algorithm:

• Start from the heads of both linked lists.
• Iterate through both linked lists simultaneously.
• At each step, add the corresponding digits from both linked lists along with any carry from the previous step.
• Calculate the sum and the carry and update the result linked list accordingly.
• If one linked list is shorter than the other, assume its remaining digits are 0.
• Continue until you reach the end of both linked lists.

Here is the algorithm written down:

public class AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, current = dummyHead;
        int carry = 0;

        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummyHead.next;
    }
}

Note: This process may sound simplistic to you, but there is a powerful lesson here. You can make a simple observation like “We need to iterate through both linked lists simultaneously,” and begin by doing the most straightforward thing possible: starting from the heads of both linked lists. Then, let the algorithm evolve from there.

If you are familiar with linked lists and basic arithmetic operations, you can see that the algorithm can be solved in O(max(m, n)). From this information, we can make further observations:

• To do better, we can solve this in:
  • O(max(m, n)) or O(1)
  • Not all algorithms fit neatly into these time-complexity buckets, but a lot of them do – especially in interviews. As a result, making this type of analysis is helpful to keep moving toward a solution.

Let’s consider each time-complexity and create more insights:

• O(max(m, n)) algorithm means we need to traverse both linked lists once.
  • The time complexity is determined by the length of the longer linked list.
  • Additional space complexity might be required if we create a new linked list to store the result.
• O(1) algorithm means constant time complexity, which is the ideal scenario.
  • Achieving O(1) typically involves optimizing the algorithm to perform operations without iterating through the entire input.

Note: Notice how we can utilize prior knowledge of time-complexity, algorithms, and data structures to generate ideas of how to solve the problem. Make sure to study the Terminology!

Let’s use the O(max(m, n)) observation. We have two linked lists representing numbers.

When we consider adding two numbers represented as linked lists:

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4

The addition of these numbers results in:

7 -> 0 -> 8

Cool. We added the numbers, but what does that give us?

We formed a new property for the input: the ability to traverse linked lists. Can we somehow exploit this property?

• Let’s begin by repeating what we did above: start from the heads of both linked lists.
  • Traverse both linked lists simultaneously while adding corresponding nodes.
  • Handle carryover if the sum exceeds 9.
• While we added the numbers, we did find a pattern:
  • We can perform addition digit by digit while traversing the linked lists.
  • We need to handle carryover from one digit to the next.
• Let’s clarify some of the things we are noticing:
  • The sum of each digit is the sum of the corresponding digits in both linked lists plus any carryover from the previous digits.
  • We need to handle carryover efficiently to avoid errors in the final result.

Let’s recap:

1. By traversing both linked lists, we found a pattern for adding numbers digit by digit.
2. Then, by analyzing the pattern, we realized that we need to handle carryover efficiently.

Note: Leaping to this conclusion is not always straightforward. However, with a lot of practice, and by using the “start from the heads” tactic, you will be able to find these types of insights.

These observations give us an O(max(m, n)) algorithm:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummy.next;
    }
}

However, this is the wrong answer!

The question requires us to return the result as a linked list, not just the sum!

If the question asked us to return the sum, this approach would be perfectly fine. That being said, it is still possible to solve the question using this method; you will just have to create a new linked list to store the result.

A mistake such as this is a great lesson! You can now put this observation in your bag of tools: “If the question requires the result as a linked list, then returning just the sum might not be the optimal solution.”

Can we do better than O(max(m, n))? Yes.

Let’s try to optimize the approach:

• The O(max(m, n)) solution involves traversing both linked lists and performing addition digit by digit.
• Is there a way to directly determine the result without iterating through the entire input?

Let’s write down what we have:

• l1: 2 -> 4 -> 3
• l2: 5 -> 6 -> 4

There are a few possible next steps:

• Sometimes, a solution will immediately pop into your head. This is the best-case scenario. It means that you are familiar with the concepts of the question because of your dedicated practice!
• Other times, you will have no idea how to proceed next. This can cause panic during an interview.
  • Luckily, you now know what to do: start from the heads of both linked lists.

By starting from the heads of both linked lists, we have the following variables:

• l1: 2 -> 4 -> 3
• l2: 5 -> 6 -> 4

How can you utilize these variables?

• Checking the variables individually doesn’t give us anything.
• Let’s formalize “traversing both linked lists and performing addition digit by digit” by writing a function: addTwoNumbers(l1, l2).
• We can calculate the sum and carryover for each digit in the result.
• We need to keep track of the current digit and carryover efficiently.

We have the basis for a solution: go through both linked lists and perform addition digit by digit.

Nevertheless, there are still two issues:

1. We need to return the result as a linked list, not just the sum.
2. We need to handle the case where one linked list is longer than the other.

Fixing #1 is straightforward. We can create a new linked list to store the result.

Fixing #2 is less obvious, but we can handle it by considering the case where one linked list ends before the other.

This gives us the following pseudocode:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val :0;
            int sum = x + y + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummy.next;
    }
}

Algorithm Analysis:

• Time Complexity: The algorithm traverses both linked lists once, so the time complexity is O(max(m, n)), where m and n are the lengths of the input linked lists.
• Space Complexity: The algorithm uses a constant amount of extra space, so the space complexity is O(1).

Dry Run:

Let’s dry run the algorithm with an example:

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4

1. Start from the heads of both linked lists: l1 and l2.
2. Initialize dummy and current nodes.
3. Loop through both linked lists simultaneously until both are exhausted:
   • Calculate the sum of corresponding nodes and any carryover.
   • Create a new node with the sum digit and update current.
   • Move to the next nodes in both linked lists.
4. If there is any remaining carryover after traversing both lists, add a new node for it.
5. Return the next node of dummy, which contains the result linked list.

Final Code:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummy.next;
    }
}

Testing / Reflection

During an interview, if you have the time, you want to test your code by walking through it step-by-step. It’s not uncommon to make a silly mistake.

During practice, you want to reflect on how the solving process went by asking various questions:

• What is the time complexity?
  • O(max(m, n))
• What is the space complexity?
  • O(1)
• What are some interesting observations from this problem?
  • The algorithm involves traversing both linked lists and performing addition digit by digit.
  • We need to handle carryover efficiently to avoid errors in the final result.
• What are some related problems?
  • There are other variations of this problem like adding two numbers represented as strings or arrays.

Reflection is a great step that allows us to “chunk” the learnings from the problem by connecting it to existing ideas.

What else can you think of? Send feedback!

P.S. you can try it @ https://leetcode.com/problems/add-two-numbers/