链表加法产生不正确的结果

Question

这是我试图从这个 leetcode问题中解决的一个简单问题的一些 python 代码。给定两个非空链表，代表两个非负整数。这些数字以相反的顺序存储，并且它们的每个节点都包含一个数字。将这两个数字相加并将其作为链表返回。您可以假设这两个数字不包含任何前导零，除了数字 0 本身。例子：  Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)   Output: 7 -> 0 -> 8   Explanation: 342 + 465 = 807.我无法弄清楚我的代码中的错误在哪里。运行时代码的输出在底部。import unittestdef addTwoNumbers(l1, l2):    Rhead1 = reverseLL(l1) # 3 -> 4 -> 2    Rhead2 = reverseLL(l2) # 4 -> 6 -> 5    node1 = Rhead1    node2 = Rhead2    carry = 0    newLL = None    while node1 and node2:        arith = node1.data + node2.data + carry        # print('node1: {0} + node2: {1} + carry: {2} = arith: {3}'.format(node1.data, node2.data, carry, arith))        carry = 0        if arith >= 10: carry, arith = divmod(arith, 10)                if newLL: newLL.next = Node(arith)        else: newLL = Node(arith)        node1, node2 = node1.next, node2.next        return newLLdef reverseLL(head):    prev = None    node = head    while node:        next = node.next        node.next = prev        prev = node        node = next        return prevclass Node:    def __init__(self, data, next=None):        self.data, self.next = data, next        def __str__(self):        string = str(self.data)        if self.next:            string += ' -> ' + str(self.next)        return stringclass Test(unittest.TestCase):    def test_addTwoNumbers(self):        head1 = Node(2, Node(4, Node(3, None)))    # (2 -> 4 -> 3)        head2 = Node(5, Node(6, Node(4, None)))    # (5 -> 6 -> 4)        expected = Node(7, Node(0, Node(8, None))) # (7 -> 0 -> 8)        print('actual:',str(addTwoNumbers(head1, head2)))        print('expected:',str(expected))        # self.assertAlmostEqual(str(addTwoNumbers(head1, head2)), str(expected))if __name__ == '__main__':    unittest.main() 输出：actual: 7 -> 8expected: 7 -> 0 -> 8我在哪里没有得到预期的结果？我傻眼了，我不知道为什么我的代码不起作用。请帮忙

Answer 1

问题在于您的 newLL 变量以及您如何将数字附加到链表中。您已经创建了该列表的头部，并且最多使用 newLL.next 上升到第二个值，但是您没有遍历列表以添加更多值。这是一个可能的解决方案：

def addTwoNumbers(l1, l2):

    Rhead1 = reverseLL(l1) # 3 -> 4 -> 2

    Rhead2 = reverseLL(l2) # 4 -> 6 -> 5

    node1 = Rhead1

    node2 = Rhead2

    carry = 0

    newLL = None

    temp = None

    while node1 and node2:

        arith = node1.data + node2.data + carry

        # print('node1: {0} + node2: {1} + carry: {2} = arith: {3}'.format(node1.data, 

        #node2.data, carry, arith))

        carry = 0

        if arith >= 10: carry, arith = divmod(arith, 10)

    

        if newLL: 

            temp.next = Node(arith)

            temp = temp.next

        else: 

            newLL = Node(arith)

            temp = newLL

        node1, node2 = node1.next, node2.next

    return newLL

Answer 2

干得好使用unittest和carry, arith = divmod(arith, 10)！

不确定你的错误，但我们可以使用哨兵节点并更容易地解决问题。

这会过去：

class Solution:

    def addTwoNumbers(self, a, b):

        carry = 0

        sentinel = p = ListNode(0)

        while a or b or carry:

            if a:

                carry, a = carry + a.val, a.next

            if b:

                carry, b = carry + b.val, b.next

            carry, val = carry // 10, carry % 10

            p.next = p = ListNode(val)

        return sentinel.next

参考

• 有关其他详细信息，您可以查看讨论区。有很多公认的解决方案，其中包含各种语言和解释、高效的算法以及渐近时间/空间复杂性分析^1、2。