leetcode添加两个数字循环

Question

我正在研究LeetCode问题2. Add Two Numbers：

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

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

我没有通过其中一个测试用例，其中l1=[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

Answer 1

两个问题：

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

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

其他一些评论：

• 如果只在已经准备好节点的值时创建节点，我会发现代码不会那么混乱。然后可以调用ListNode(temp)或传递所需值的东西。这样，您还可以消除循环中的条件中断

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

• 如果将carry设为整数而不是布尔值，则更容易处理：只需将进位相加，然后通过将temp除以10来计算其新值

• 实际上不需要处理列表可能为[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