The problem

Understanding the problem, we are supposed to basically add two numbers that are in reversed order. Let us understand what this means exactly.

Breakdown

We are given the following numbers:

l1 = [1, 5, 7, 2, 6]
l2 = [1, 8, 3]

In number terms, l1 means 62751 and l2 is 381. That is what they mean by the reverse part. This is how you can add them together:

  6 2 7 5 1
+     3 8 1
-----------
  6 3 1 3 2

Then you reverse the answer to get something like this:

answer: [2, 3, 1, 3, 6]

Thought process

With the above breakdown, the initial approach was to solve the problem by following these steps:

• Reverse each of the linked lists from [1, 5, 7, 2, 6] => 62751 and [1, 8, 3] => 381
• Add the numbers together: 62751 + 381 = 63132, then reverse the answer
• Convert the reversed answer into a linked list

Sounds simple, right? Let us explore this solution.

1. Reverse the linked list

There is no linked list method like .reverse() that can be simply used to reverse the linked list. So the approach here is to traverse (loop over) the linked list using the nodes and then convert the whole linked list into a string.

Because we know how to reverse a string, right? Let us see the code in action for this:

function convertListToString(current: ListNode): string {
    if (current.next === null) return String(current.val);
    return String(current.val) + convertListToString(current.next);
}

Recursion is used for this approach:

• Basically, we check if we are on the last node or not by checking if the next node is null. If yes, we simply return the value of that node as a string.
• If not, we add the current node value with the value of the next node.

Hope this makes sense. If not, please checkout this recursion video to help you get started with recursions.

Reverse string

For the string reversal, the following code is used:

function reverseString(value: string, current: number): string {
    if (current === 0) return value[current];
    return value[current] + reverseString(value, current - 1);
}

Again, recursion is used for this as well.

2. Add the numbers

This is the easy step, where the numbers get added. But first they have to be converted from a string to a number using the Number() class:

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const convertL1ToString = convertListToString(l1);
    const l1ReversedNumber = Number(reverseString(convertL1ToString, convertL1ToString.length - 1));

    const convertL2ToString = convertListToString(l2);
    const l2ReversedNumber = Number(reverseString(convertL2ToString, convertL2ToString.length - 1));

    const sumString = String(l1ReversedNumber + l2ReversedNumber);
    // Reverse the sumString and then convert it to a linked list
}

Just a reminder, the answer from the example used above is: 62751 + 381 = 63132. The reversed answer will then be 23136.

3. Convert to Linked List

Now we are just left with reversing the sumString into a linked list. Here is the code for that:

function convertStringToList(numberString: string): ListNode {
    let head: ListNode = new ListNode(Number(numberString[0]));
    let currentNode: ListNode = head;
    let currentIndex = 1;

    while (currentIndex < numberString.length) {
        let nextNode = new ListNode(Number(numberString[currentIndex]));
        currentNode.next = nextNode;
        currentNode = nextNode;
        currentIndex++;
    }

    return head;
}

Let's break this code down and make it simple:

Breakdown:

Here is a detailed breakdown:

• We take the first element of the string which is 2, then create a linked list head (start of the linked list), which gives us 2 -> null where val = 2 and next = null.
• Then we set the currentNode to be the head. This is because we do not want the head to be overridden, hence a separate node is created for tracking changes.
• A while loop is used here. From there, a new node is created with the next number on the numberString, say 3 -> null.
• This gets linked to the head to give us 2 -> 3 -> null by setting currentNode.next to the new node.
• Then currentNode is re-assigned and currentIndex is incremented.

Full thought solution

This is the full solution if we combine all that has been done above:

function convertStringToList(numberString: string): ListNode {
    let head : ListNode = new ListNode(Number(numberString[0]), null);
    let currentNode : ListNode = head;
    let current = 1;

    while (current < numberString.length) {
        let nextNode = new ListNode(Number(numberString[current]), null);
        currentNode.next = nextNode;
        currentNode = nextNode;

        current++;
    }

    return head;
}

function convertListToString(current: ListNode) : string {
    if (current.next === null) return String(current.val);
    return String(current.val) + convertListToString(current.next);
}

function reverseString(value: string, current: number): string {
    if (current === 0) return value[current];
    return value[current] + reverseString(value, current - 1);
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const convertL1ToString = convertListToString(l1);
    const l1ReversedNumber = Number(reverseString(convertL1ToString, convertL1ToString.length - 1));

    const convertL2ToString = convertListToString(l2);
    const l2ReversedNumber = Number(reverseString(convertL2ToString, convertL2ToString.length - 1));

    const sumString = String(l1ReversedNumber + l2ReversedNumber);
    return convertStringToList(reverseString(sumString, sumString.length - 1));
};

The thought problem

The solution from the thought process works, but not for all cases. Here is an example where it will not work:

l1 = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
l2 = [5,6,4]

• The reason this fails is that JavaScript's Number type uses 64-bit floating point (IEEE 754), which can only safely represent integers up to 2^53 - 1 (i.e. Number.MAX_SAFE_INTEGER = 9007199254740991).
• The number represented by l1 far exceeds this limit, meaning precision is lost during the conversion from string to number.
• As a result, the addition produces an incorrect value and the final linked list will be wrong.

From a time complexity perspective, the thought process solution is also less efficient. Converting the linked list to a string is O(n), reversing the string is O(n), and converting back to a linked list is O(n), but these operations are stacked and involve additional overhead from string and number conversions, making the overall approach more costly in practice.

The solution

Instead of converting the linked list to a string and performing reversals, we can look at this problem through a math lens.

If you look at the problem closely, there is no need to do any reversal or string conversions. The linked lists are already in the correct positional order — units first, then tens, then hundreds, and so on:

  units   tens   hundreds   thousands   ten-thousands
[ 1,      5,     7,         2,          6 ]
  units   tens   hundreds
[ 1,      8,     3 ]

This means all we need to do is add units to units, tens to tens, and so on, just like standard column addition:

  1 5 7 2 6
+ 1 8 3
-----------
  2 3 1 3 6

The answer already comes out in the reversed format that is expected.

Math solution breakdown

Let us think of how we can solve this with just math, no coding for now, just the addition part:

  1 5 7 2 6
+ 1 8 3
-------------
  2

• We will start with adding 1 + 1 which gives us 2
• Moving on

      1 -> carried over
  1 5 7 2 6
+ 1 8 3
-------------  13 -- use the 3
  2 3

• We then added 5 + 8 which gave us 13.
• From the 13 we used the 3 to display on the answer
• And we carried the 1 over for the third calculation

        1 -> carried over
  1 5 7 2 6
+ 1 8 3
-------------  11 -- use the 1
  2 3 1

• The same thing here as well. Add the 7 + 3 + 1 where the 1 is basically a carry over from the previous execution.
• From the 11 we used the 1 to display on the answer
• And we carried the 1 over for the third calculation

        1
  1 5 7 2 6
+ 1 8 3
-------------
  2 3 1 3

• Then 2 + 1 gives us 3, where the 1 comes from the carry over of the previous execution

Implementing the math solution

Breaking down of the code above combined with the math logic above.

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const headNode = new ListNode(0); // Initial node
    let currentNode = headNode; // Node that will carry the changes
    let carryOver = 0; // The carry over

    while (l1 !== null || l2 !== null || carryOver !== 0) {
        const value1 = l1 ? l1.val : 0; // Where there are no values for l1, I will use zero
        const value2 = l2 ? l2.val : 0; // Where there are no values for l2, I will use zero

        const sum = value1 + value2 + carryOver;
        carryOver = Math.floor(sum / 10);

        let nextNode = new ListNode(sum % 10);

        // Used the same approach as above when I was converting the string to a linked list
        currentNode.next = nextNode;
        currentNode = nextNode;

        if (l1) l1 = l1.next; // If l1 still has the next node, use that node
        if (l2) l2 = l2.next; // If l2 still has the next node, use that node
    }
                                       // start pointer
                                            // |
    // Since the head starts with a zero = [0, 2, 3, 1, 3, 6], my start will be the second node
    return headNode.next; 
};

The code should be straight forward now, let me just explain the carry over and the display number calculation with code:

• When we add number where the answer is more than ten, we would have a carry over situation.

• We know that number, let me say that is m it will be within these limits 10 <= m < 20. Which means that we know the number is a unit of tens.

• Let us take 5 + 8 which gave us 13 for example. We know that from the 13, the 1 will be carried over, and the 3 will be the displayed (added to the node) number.

• With code the carry over is calculated like this Math.floor(13 / 10) which gives us 1.

• Then the display number (used to create a next node) is calculated like this 13 % 10. Which means, how many times does 10 go into 13? That is once, and what is the remainder? The remainder is 3, hence we use the 3

Time complexity

The time complexity for this solution is O(n) where n is the length of the longest linked list between l1 and l2.

question = "Hope this helps, does it?\n"
answer = input("Enter (Y/N):\n-> ")

if answer == "N":
  print("Please let me know via whatsapp or email")
else:
  print("Glad that helped. Wishing you all the best")

Thank you for you time. Have a awesome day.