Linkedlist加法产生不正确的结果

Question

下面是一些python代码，用于解决一个简单的问题，我正试图从这个leetcodequestion解决这个问题

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 contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

  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

很好地使用了unittest和carry, arith = divmod(arith, 10)

---

不确定您的bug，但我们可以使用sentinel节点，从而更轻松地解决问题

这将通过：

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

---

参考资料

• 有关更多详细信息，请参见Discussion Board。有许多公认的解决方案，其中包括各种languages和解释、有效算法以及渐近time/space复杂性分析^1、2

Answer 2

问题在于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