在Python中合并两个排序的链接列表时，“NoneType”对象没有属性“next”

Question

我用Python编写了一个函数来合并两个排序的链表。这是代码：-

 class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

class LinkedList:

    def __init__(self):

        self.head = None

    def append(self, data):

        new_node = Node(data)

        if self.head is None:

            self.head = new_node

            return

        last_node = self.head

        while last_node.next is not None:

            last_node = last_node.next

        last_node.next = new_node

    

    def print(self):

        cur_node = self.head

        while cur_node.next is not None:

            print(cur_node.data, "-> ", end='')

            cur_node = cur_node.next

        print(cur_node.data)

def merge(l1, l2):

    cur_node1 = l1.head

    cur_node2 = l2.head

    l3 = LinkedList()

    while cur_node1.next is not None or cur_node2.next is not None:

        if cur_node1.data > cur_node2.data:

            l3.append(cur_node2.data)

            cur_node2 = cur_node2.next

        else:

            l3.append(cur_node1.data)

            cur_node1 = cur_node1.next

    if cur_node1.next is None:

        l3.append(cur_node1.data)

        while cur_node2.next is not None:

            l3.append(cur_node2.data)

            cur_node2 = cur_node2.next

        l3.append(cur_node2.data)

    elif cur_node2.next is None:

        l3.append(cur_node2.data)

        while cur_node1.next is not None:

            l3.append(cur_node1.data)

            cur_node1 = cur_node1.next

        l3.append(cur_node1.data)

    return l3

ll1 = LinkedList()

ll2 = LinkedList()

ll1.append(12)

ll1.append(45)

ll1.append(69)

ll1.append(70)

ll2.append(1)

ll2.append(2)

ll2.append(99)

ll2.append(100)

ll3 = merge(ll1, ll2)

ll3.print()

这里发生了什么？我不明白。我尝试在合并函数的 while 循环中运行没有 or 语句的代码。效果很好。显然问题出在 while 语句中。有人可以帮忙吗？

Answer 1

问题出现在您的第一个循环中：while cur_node1.next is not None or cur_node2.next is not None:这意味着两个节点之一可以具有next属性None。如果该节点的数据也小于另一个节点中的数据，则该节点变量将设置为None。然后while再次评估条件，并产生错误，因为该None值没有next属性......cur_nodeX.next通过检查属性而None不是其本身，实际上使算法变得过于复杂cur_nodeX。因此，在第一个循环完成后，您仍然需要从两个列表中添加节点。此外，您的代码假设两个列表都不为空。while因此，根据当前节点而不是它们的属性来设置条件next：def merge(l1, l2):    cur_node1 = l1.head    cur_node2 = l2.head    l3 = LinkedList()    while cur_node1 is not None or cur_node2 is not None:        if cur_node1 is None or cur_node2 is not None and cur_node1.data > cur_node2.data:            l3.append(cur_node2.data)            cur_node2 = cur_node2.next        else:            l3.append(cur_node1.data)            cur_node1 = cur_node1.next    return l3

Answer 2

对于任何想知道的人来说，这都是有效的。def merge(l1, l2):cur_node1 = l1.headcur_node2 = l2.headl3 = LinkedList()while True:&nbsp; &nbsp; if cur_node1 is None:&nbsp; &nbsp; &nbsp; &nbsp; while cur_node2.next is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur_node2 = cur_node2.next&nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; elif cur_node2 is None:&nbsp; &nbsp; &nbsp; &nbsp; while cur_node1.next is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node1.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur_node1 = cur_node1.next&nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node1.data)&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; if cur_node1.data > cur_node2.data:&nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; cur_node2 = cur_node2.next&nbsp; &nbsp; elif cur_node1.data < cur_node2.data:&nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node1.data)&nbsp; &nbsp; &nbsp; &nbsp; cur_node1 = cur_node1.nextreturn l3

Answer 3

打印“1 -> 2 -> 12 -> 45 -> 69 -> 70 -> 99 -> 100”def merge(l1, l2):&nbsp; &nbsp; cur_node1 = l1.head&nbsp; &nbsp; cur_node2 = l2.head&nbsp; &nbsp; l3 = LinkedList()&nbsp; &nbsp; while cur_node1 and (cur_node1.next is not None or cur_node2.next is not None):&nbsp; &nbsp; &nbsp; &nbsp; if cur_node1.data > cur_node2.data:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur_node2 = cur_node2.next&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node1.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur_node1 = cur_node1.next&nbsp; &nbsp; &nbsp; &nbsp; if cur_node1.next is None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l3.append(cur_node1.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while cur_node2.next is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cur_node2 = cur_node2.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; elif cur_node2.next is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node2.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while cur_node1.next is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node1.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur_node1 = cur_node1.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.append(cur_node1.data)&nbsp; &nbsp; return l3