LeetCode - 2. 两个数字相加

Question

我正在尝试解决这个 Leetcode 问题，我已经实现了一个似乎适用于大多数情况的解决方案，但它在特定情况下失败了。这是提供的代码：

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

它成功处理了一般情况，但当使用

l1 = [2,4,9]

和

l2 = [5,6,4,9]

等输入进行测试时，输出为

[8,9,8,5]

，而预期结果为

[7,0,4,0,1]

。

我的策略是累加链表中的值，计算它们的总和，然后创建一个新的链表来存储结果。我观察到其他使用不同方法的解决方案，但我不确定为什么我当前的实现在某些情况下失败。任何见解或建议将不胜感激。

Answer 1

问题出在你的函数的第一部分。从列表中获得的数值是错误的，因为列表在其头节点中具有“最低”有效数字，然后在其他节点中具有较高的有效数字。您的代码解释第一个节点具有most有效数字。 在函数的第二部分中，您做得正确：您创建的新列表将在其第一个节点中具有最低有效数字，...等等。

这是一个正确获取链表表示的值的函数：

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

现在你可以做：

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

...现在就可以了。