For better or worse, leetcode style problems have become a staple for a lot of companies in their interview process. This means we, as developers, need to understand how to solve these types of problems. The ‘how’ is very important. The art of problem solving extends far beyond DSA/Leetcode style problems which is why this post will focus on how to solve problems, not the solution itself.

Let’s get started…

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]


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

/**
 * 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: ListNode | null,
  l2: ListNode | null
): ListNode | null {}

We will use problem 2 from Leetcode, Add Two Numbers to walk through a series of steps to help us find a solution.

Restate the problem - Understand the problem

The first step we should take is restating the problem in our own words because if we can’t do that then we don’t understand the problem… Which means we can’t solve the problem.

So to do this, we would read the prompt, the code examples, constraints, any information we have basically and then formulate an understanding before putting it into words. For example:

Pull out important information:

• adding two linked-lists
• stored in reverse order
• lists will not be empty but they can be null
• each node = 1 digit
• return sum as linked list
• last node won’t be 0 unless linked list only contains 0

Piece information together

If we write out one of the example problems like so:

[2, 4, 3]
[5, 6, 4]

It looks very similar to how many of us were taught to add numbers when we were younger. We operate on a column-by-column basis and carrying over as needed.

Using our words

So based on what we know:

We need to perform a column by column addition while also keeping track of any carry overs. We start on the right hand side, and work backwards.

Now the above may seem overly simplified or lacking of information, but at this stage it is only important for us to understand the problem. By reframing the problem in terms we can understand, maths learned at school, we’ve linked the problem to something we have experience in.

The inputs, outputs and constraints

In our case the inputs and outputs seem pretty simple, we have 2 linked lists as an input and we have 1 linked list as an output.

The contraints are relatively simple as well, as in most leetcode problems they limit the range and size of numbers we have to deal with. In this case each node can only be a single digit, so 0-9 inclusive. We also don’t need to worry about leading zeros.

Items of note:

• The linked lists we have as an input are not always the same size.
• The linked list we output may be bigger than either input size, if we have to carry over for example.

The black box approach - Examples and edge cases

So now that we understand the problem, the inputs, outputs and contraints we can start putting together some examples and exploring edge cases.

For example:

[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]

We know the answer to the above would be: [6, 6, 6, 6, 6] because we just need to add the columns together, something we can do without even writing a single line of code.

This is what we mean by the black box approach. We can work out manually what the output should be given some input, the implementation details of that aren’t important at the moment, and exist inside this unknowing black box.

If we were in an interview setting we’d also confirm the inputs/outputs and any edge cases with the interviewer. Think of this as confirming a feature with a product owner/manager in a work-place setting before we start writing code.

We should put together the happy path examples, like above, where the solution is fairly simple but also explore edge cases, for example:

[9, 9, 9]
      [1]

Which should give an output of [1, 0, 0, 0]. There is no constraint against an empty list, so we should also get an example of that:

null
[1, 2, 3]

Once again, we’d confirm with the interviewer what the expected output should be but in this case we can assume it will output [1, 2, 3] (this is what leetcode expects). Basically if one of the lists is empty, then we just return the other list unchanged.

This section can take some time but fear not, this time isn’t wasted as the examples we’ve created are now tests for us to use with our implementation.

Once we’re happy with the number of examples we have, we’re ready to move on.

Leetcode often provides some examples as well, and provides the option to add more to their test suite

Working out the core operations

At this stage we’re not looking to figure out the whole solution, we want to isolate the core logic that we need to implement.

For some problems it may be very difficult to work out core operations, in those cases you may want to first brute force your way to a solution, which is discussed in the next section. I highlight this here because these steps are a guideline, not a rule, and the order isn’t always locked in place.

There are a few things we know, first our core logic will be ‘repeated’. At this stage we don’t need to worry so much about how we ‘repeat’, iterative or recursive for example, but the steps that need to happen within.

After understanding the problem we realised we will be performing column by column addition, so in code that may look something like:

sum = carry + (l1?.val || 0) + (l2?.val || 0);

We know we need to keep track of the carry as many of us will have learnt to perform addition in this way, and we need to add the carry to the next column we sum up.

We also need to perform a null check, the (li?.val || 0), because we’re working with linked lists and as outlined in the problem those lists can be of different sizes. When we reach the end of one list we will simply treat its values as 0 while we move over the remaining list.

Next, we need to get the value for the new linked list. Currently sum could be a double digit number as it is just the sum of the values in both of the input linked lists. Looking at some simple addition examples:

5 + 6 = 11
5 + 5 = 10
9 + 9 = 18

We can see we need the second digit, this is what will be the value in the output linked list. In math terms, we need the remainder after we divide sum by 10. For this we can use the modulo operator:

newDigit = sum % 10;

With this we know if sum = 11 then newDigit will equal 1. It works with single digit as well, if sum = 4 then newDigit will also equal 4.

Now, the remaining piece of the puzzle is working out what our carry is. There are many ways we could work out the carry but if we lean on math again, we can see we always want the first digit in a double digit number. How do we do that? Well we can divide by 10 and round down:

carry = Math.floor(sum / 10);

In this case when sum = 8, carry will equal 0 and when sum = 17, carry will equal 1.

With this we now have some idea of how we’re going to sum up the columns, get the value for the new linked list and caculate the carry. The core logic for our problem.

Your idea of core logic may be different, or maybe you had different solutions to the above problems. This is fine, my only suggestion here is try to focus only on the core logic and if you’re in an interview vocalise your thoughts. You want to show off how you solve problems so even if your solution is wrong the interviewer can see you know how to go about solving problems.

Brute forcing our way to a solution

The act of brute forcing is simply finding the first, simplest, solution that actually works to solve the problem. We’re not looking for the most efficient or performant, we simply want something that we think would work.

Sometimes we may find that we don’t need to do this step, after following the previous steps we may have enough knowledge to move on. The example problem we’re using here is simple enough that more experience developers would be able to move on, however eventually we will all encounter a problem where we can’t. So understanding this step may be useful to us all!

So how would we go about brute forcing a solution?

One option is convert the inputs into an easy format to deal with. So we could convert the linked lists into numbers, add them together, and then convert the result back into a linked list.

You may find a different solution here, and that is perfectly fine. The goal of brute forcing is finding something that gives you an answer.

This would likely work for most inputs but we’d have a few concerns, the main one is numbers may overflow. The problem specifies that: The number of nodes in each linked list is in the range [1, 100].. So we could have numbers 100 digits long, most programming languages do not have built in numeric types that can handle such large numbers.

So why bother doing this brute force approach if the solution isn’t performant, efficient or work for all inputs?

It gets us thinking about the problem, we now have a solution that we think would work in most cases but isn’t perfect. We can use this as a base to build a better, more resilient, solution.

I want to reiterate, this step is optional. I personally only brute force when I’m not sure how to move forward with a solution. Often times the act of brute forcing allows me to see the problem from different angles, find things that work/don’t work and build a solution from there.

It is time to plan!

Now we’re ready to start planning our solution, this step would also include deciding on any data structures or algorithms we need for this problem. In our case we already have the data structure, the linked list, and there are no searching or sorting algorithms we need to use.

From our brute forcing we know we simply can’t convert to a number, add together and then back to a linked list. What we need, as is common when working with linked lists, are pointers. We’d maintain pointers on l1 and l2 and move those pointers as we sum up the columns.

When creating a new linked list it helps to have a dummy node, dummy = new Node(0). We will then add nodes to this and return dummy.next, omitting the dummy node, from our function.

We also need a tail reference that will act as a pointer to dummy

Lastly, the carry needs to be maintained.

With that, we have a skeleton of a plan. We have our core logic, broken down how we will work with the linked lists and are ready to move onto code!

The almost code - Pseudocode

Depending on our own knowledge, and the complexity of the problem, it can be useful to write out some pseudocode.

In an interview setting this can be really useful as it puts your solution in front of the interviewer. So even if you run out of time you have something to show and talk about.

Like the brute force step, this step is optional, however highly recommended. Take the following as an example:

carry = 0
dummy = new Node(0)
tail = dummy
p1 = l1, p2 = l2

while p1 or p2 or carry:
  v1 = p1?.val ?? 0
  v2 = p2?.val ?? 0
  sum = v1 + v2 + carry
  tail.next = new Node(sum % 10)
  carry = sum / 10 (round down)
  tail = tail.next
  if p1: p1 = p1.next
  if p2: p2 = p2.next

return dummy.next

This is all of our planning written down in a readable format, at this stage we’d be able to test a few of our examples and discover any issues within our solution. We’d be able to discuss this with the interviewer, and more importantly the interviewer gets to see our thought process and intended solution.

When it comes to actually writing the code we no longer have to think about the logic, only the syntax.

But as developers writing code is oftentimes the most fun part so…

Finally… The code!

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let carry = 0;
  const dummy = new ListNode(0);
  let tail = dummy;
  let p1 = l1,
    p2 = l2;

  while (p1 !== null || p2 !== null || carry > 0) {
    const v1 = p1 ? p1.val : 0;
    const v2 = p2 ? p2.val : 0;
    const sum = v1 + v2 + carry;
    tail.next = new ListNode(sum % 10);
    carry = Math.floor(sum / 10);
    tail = tail.next!;

    if (p1) p1 = p1.next;
    if (p2) p2 = p2.next;
  }

  return dummy.next;
}

Using the psuedocode as a base, we’re able to go line by line and easily implement our proposed solution.

and we now have our solution!

By using these steps as a guideline we can approach problems of all difficulties in a structured way and hopefully find ourselves with a solution.