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

Question

我用Python编写了一个函数来合并两个排序的链表。这是代码：- class Node:    def __init__(self, data):        self.data = data        self.next = Noneclass 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 l3ll1 = 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.head

cur_node2 = l2.head

l3 = LinkedList()

while True:

    if cur_node1 is None:

        while cur_node2.next is not None:

            l3.append(cur_node2.data)

            cur_node2 = cur_node2.next

        l3.append(cur_node2.data)

        break

    elif cur_node2 is None:

        while cur_node1.next is not None:

            l3.append(cur_node1.data)

            cur_node1 = cur_node1.next

        l3.append(cur_node1.data)

        break

    if cur_node1.data > cur_node2.data:

        l3.append(cur_node2.data)

        cur_node2 = cur_node2.next

    elif cur_node1.data < cur_node2.data:

        l3.append(cur_node1.data)

        cur_node1 = cur_node1.next

return l3

Answer 3

打印“1 -> 2 -> 12 -> 45 -> 69 -> 70 -> 99 -> 100”

def merge(l1, l2):

    cur_node1 = l1.head

    cur_node2 = l2.head

    l3 = LinkedList()

    while cur_node1 and (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 not 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