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

Question

这是我试图从这个 leetcode问题中解决的一个简单问题的一些 python 代码。

给定两个非空链表，代表两个非负整数。这些数字以相反的顺序存储，并且它们的每个节点都包含一个数字。将这两个数字相加并将其作为链表返回。

您可以假设这两个数字不包含任何前导零，除了数字 0 本身。

例子：

  Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
  Output: 7 -> 0 -> 8
  Explanation: 342 + 465 = 807.

我无法弄清楚我的代码中的错误在哪里。运行时代码的输出在底部。

import unittest

def 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 newLL

def reverseLL(head):

    prev = None

    node = head

    while node:

        next = node.next

        node.next = prev

        prev = node

        node = next

    

    return prev

class 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 string

class 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 -> 8

expected: 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。