以下是我试图从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
我哪里没有得到预期的结果？我目瞪口呆，不知道为什么我的代码不起作用。请帮助
问题在于您的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
使用unittest和carry, arith = divmod(arith, 10)很好！
不确定您的错误，但我们可以使用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
参考文献
- 有关更多详细信息，请参阅讨论板。有很多公认的解决方案，包括各种语言和解释，有效的算法，以及渐近时间/空间复杂性分析1，2