时间戳

首页 > 解决方案 > leetcode 两个数字相加循环

python - leetcode 两个数字相加循环

问题描述

我正在解决 LeetCode 问题2。添加两个数字：

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

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

我在其中一个测试用例中失败了，其中 l1 = [9,9,9,9,9,9,9] 和 l2 = [9,9,9,9]。我正在输出 [8,9,9,9,9,1]，正确的输出是 [8,9,9,9,0,0,0,1]。我的python代码发布在下面。我很确定我的第一个 while 循环 ( l1 and l2) 工作正常。我不知道在第二个循环 ( while l1) 中我需要更改什么以获得正确的输出。

if l1 == [0] and l2 == [0]:
    return ListNode()
if l1 == [0]:
    return l2
if l2 == [0]:
    return l1

carry = False
sum_num = ListNode()
head = sum_num

while l1 and l2:
    temp = l1.val + l2.val
    if carry:
        temp += 1
        carry = False
    if temp >= 10:
        carry = True
        sum_num.val = temp % 10
    if temp < 10: #changed these from an if because not triggering correctly because double if
        sum_num.val = temp
    l1 = l1.next
    l2 = l2.next
    if not l1 or not l2:
        break
    sum_num.next = ListNode()
    sum_num = sum_num.next

while l1:
    temp2 = l1.val
    if carry:
        temp2 += 1
        carry = False
    if temp2 >= 10:
        carry = True
        sum_num.val = temp % 10
    if temp2 < 10:
        sum_num.val = temp
    l1 = l1.next
    if not l1:
        break
    sum_num.next = ListNode()
    sum_num = sum_num.next

while l2:
    temp3 = l2.data
    if carry:
        temp3 += 1
        carry = False
    if temp3 >= 10:
        carry = True
        sum_num.val = temp % 10
    if temp3 < 10:
        sum_num.val = temp
    l2 = l2.next
    if not l2:
        break
    sum_num.next = ListNode()
    sum_num = sum_num.next

if carry:
    sum_num.val = 1

return head

标签： pythonlinked-list

解决方案

两个问题：

  • 您在第二个和第三个循环中有引用temp而不是temp2和temp3，这显然会导致错误的结果。

  • 当所有循环都完成并且有进位时，你用 1覆盖最后添加的节点的值。这是错误的。您需要一个新节点来存储进位。

其他一些评论：

  • 如果您只在已经准备好它的值时才创建一个节点，我会发现代码不那么令人困惑。然后你可以调用ListNode(temp)或其他东西——传递它需要的值。这样，您还可以取消循环中的条件中断。

  • 您有三个带有代码重复的循环。避免这种重复，让您的第一个循环继续，而列表引用中的任何一个都不是 None。因此，将 while 条件更改为 OR 并让循环体处理列表引用可能为 None 的情况。

  • 如果您carry使用整数而不是布尔值，则更容易使用：您只需添加进位并通过除以temp10 来计算其新值。

  • 没有必要处理列表可能为 [0] 的特殊情况。确实，这可能会为这些特定情况带来一些速度优势，但我会将它们排除在外。

这是使用上述注释更新的代码：

carry = 0  # Integer instead of boolean -- easier to work with here
sum_num = None  # Don't create a node yet
head = None

while l1 or l2:  # Changed condition to avoid code repetition in 2 more loops
    temp = carry  # Since carry is an int, we can just add this 0 or 1.
    if l1:  # Deal gracefully with a None
        temp += l1.val
        l1 = l1.next
    if l2:
        temp += l2.val
        l2 = l2.next
    carry = temp // 10  # Simple way to set the new carry
    new_node = ListNode(temp % 10)  # Create node now that you know the value
    if head: 
        sum_num.next = new_node
    else:  # First time
        head = new_node
    sum_num = new_node

# No code repetition here. Just one more thing to do:
if carry:
    sum_num.next = ListNode(1)

return head

推荐阅读