[FIXED] LeetCode - 2. Add Two Numbers

Issue

I'm attempting to address Leetcode problem 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.

I've implemented a solution that seems to work for most cases, but it fails for specific scenarios. Here's the provided code:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        num1 = 0
        num2 = 0
        while l1:
            num1 = (num1*10) + int(l1.val)
            l1 = l1.next
        while l2:
            num2 = (num2*10) + int(l2.val)
            l2 = l2.next
        res = num1 + num2
        dummy = ListNode()
        n = dummy
        for i in range(len(str(res))):
            n.next = ListNode(res % 10)
            res = res // 10
            n = n.next
        return dummy.next

It successfully handles general cases, but when tested with inputs like l1 = [2,4,9] and l2 = [5,6,4,9], the output is [8,9,8,5], while the expected result is [7,0,4,0,1].

My strategy is to accumulate the values from the linked lists, calculate their sum, and then create a new linked list to store the result. I've observed other solutions that use different approaches, but I'm unsure why my current implementation is failing in certain scenarios.

Where is my mistake?

Solution

The problem is in the first part of your function. The numerical value you get from a list is wrong, because the list has the least significant digit in its head node, and then the more significant digits in the other nodes. Your code interprets the first node has having the most significant digit.

In the second part of your function, you do it correctly: the new list that you create will have the least significant digit in its first node, ...etc.

Here is a function that correctly gets the value that is represented by a linked list:

class Solution:
    def valueof(self, node):
        power = 1
        num = 0
        while node:
            num += node.val * power
            power *= 10
            node = node.next
        return num

Now you can do:

        res = self.valueof(l1) + self.valueof(l2)

...and it will work.

Answered By - trincot