时间戳

首页 > 解决方案 > 为什么在反转链表并处理新链表的头部后出现 NoneType 错误？

python - 为什么在反转链表并处理新链表的头部后出现 NoneType 错误？

问题描述

我正在编写代码来回答以下问题：“对于包含正整数（并且至少有一个节点）的两个链​​表 l1 和 l2，将它们的总和作为链表返回。”

例如：

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

我编码的方式是反转两个链表，然后添加它们（添加这就是添加两个数字的方式）

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1==[0]:
            return l2 
        
        if l2==[0]:
            return l1
        
        #Reversing both linked lists l1 & l2
        prev = None
        pointer = l1

        while pointer:
            curr = pointer.next 
            pointer.next = prev
            prev = pointer
            pointer = curr

        prev2 = None
        pointer2 = l2

        while pointer2:
            curr2 = pointer2.next 
            pointer2.next = prev2
            prev2 = pointer2
            pointer2 = curr2

        #prev and prev2 are the heads of the reversed linked list(I've tested this) 


        #Creating a new linked list that is the addition of the two reversed linked list
        l3=ListNode(0)
        start_l3 = l3
        carry = 0 

        while prev or prev2:
            if prev.val + prev2.val >9:
                carry =1
            else:
                carry = 0
            s = prev.val + prev2.val + carry
            l3.next = ListNode(s)
            l3=l3.next
            prev=prev.next
            prev2=prev2.next

        if carry ==1:
            l3.next = ListNode(1)

        return start_l3.next

当我为上面给出的输入运行它时，我得到一个“NoneType object has no attribute val for the lineif prev.val + prev2.val >9:

任何想法为什么会这样？因为当我测试时prev and prev2；它似乎确实返回了反向链表。

标签： pythonlinked-list

解决方案

错误的原因是你不能假设两者 都不是。您的条件仅保证其中至少有一个不是，但不能两者兼而有之。所以这意味着你仍然需要在循环体内进行检查。prevprev2NonewhileNoneNone

还有一些其他的问题：

  • l1==[0]:是不正确的。这个比较的左边是一个链表实例，而右边是一个标准列表。这些比较将永远存在False，因此您可以省略它们

  • 您将 加到carry错误的总和中。您应该将carry上一次迭代中的 加到当前总和中，因此目前事情的顺序是错误的。

  • 结果列表应该颠倒过来。您可以通过为每个节点添加前缀l3而不是附加它来即时执行此操作。这也使得ListNode(0)在最终循环之前没有必要创建一个虚拟对象。你可以从None.

  • 您的代码会改变原始输入列表。这在代码挑战网站上是可以接受的，而且效率很高，但这是不好的做法。调用者不应该对他们作为输入提供的列表已通过调用此addTwoNumbers函数而反转而感到不愉快的惊讶。您可以通过多种方式解决此问题，但最简单的方法可能是再次反转它们以撤消该操作。

  • 为避免代码重复，您应该创建一个reverse函数

我假设ListNode构造函数可以使用第二个参数来初始化它的next引用：

class ListNode:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

那么更正后的代码可能是：

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        def reverse(lst: ListNode):
            prev = None
            node = lst
            while node:
                curr = node.next 
                node.next = prev
                prev = node
                node = curr            
            return prev

        #Reversing both linked lists l1 & l2
        l1 = reverse(l1)
        l2 = reverse(l2)

        #Creating a new linked list that is the addition of the two reversed linked list
        node1 = l1
        node2 = l2
        l3 = None
        carry = 0 

        while node1 or node2:
            added = carry  # The carry from the previous iteration should be used
            if node1:  # You must have this check
                added += node1.val
                node1 = node1.next
            if node2:
                added += node2.val
                node2 = node2.next
            carry = added // 10  # Simpler way to get the carry
            l3 = ListNode(added % 10, l3)  # Prefix(!) the new node

        if carry == 1:
            l3 = ListNode(1, l3)

        # Restore the input lists:
        reverse(l1)  
        reverse(l2)
        return l3

补充说明

关于节点在最终列表中的前缀l3：

这是这样做的主要声明：

l3 = ListNode(added % 10, l3)

让我们分解一下：

使用两个参数调用构造函数：

  • val = added % 10：这是一个数字，所以如果added是 14，这个表达式将计算为 4（1 将进入进位）。
  • nxt = l3：这是当前（不完整的）列表。这是第一次None。

然后构造函数将这些值分配为正在初始化的新节点的属性：

self.val = val
self.next = nxt

所以在这里我们看到 , 的值nxt被分配给新节点的next属性。当我们作为参数传递l3时，我们实际上是在做：

self.next = l3

通过该语句，我们有效地将新节点添加到列表中：新节点成为列表的第一个节点。此外，self充当该列表的头部，该列表现在长了一个节点。我们想要跟踪这个新的头，因此我们将新节点分配回l3：

l3 = ListNode(added % 10, l3)

和第一次一样l3，None这只会创建一个单节点列表，其next属性是 that None。但是第二次执行时，我们得到一个新节点，它next引用“现有”节点，所以现在我们有一个包含两个......等的列表。

有时用一个像 一样的虚拟节点启动一个链表会派上用场ListNode(0)，然后可以将其删除。然而，在这个修改后的算法中没有任何帮助，所以我们从 开始None，在循环的第一次迭代之后，它将作为构造函数的第二个参数，而ListNode构造函数又将使用它来初始化next新节点的属性。这个新节点将保留在列表的尾部，因为其他节点都以它为前缀。

推荐阅读