我按顺序合并两个排序的链表的实现到底有什么问题？

Question

[我正在尝试在Python3中编写一个函数，以在维护顺序的同时将两个排序的链表合并到另一个列表中，但似乎陷入了无限循环。

class Node:
    def __init__(self,data):
        self.data  = data 
        self.next  = None #next pointer is None at the moment

class LinkedList:
    def __init__(self):
        self.head = None
    def printLinkedList(self):
        currentPointer = self.head
        while (currentPointer!=None):
            print(currentPointer.data)
            currentPointer = currentPointer.next


def mergeTwoSortedLists(linkedList1,linkedList2):
    linkedList1Pointer = linkedList1.head
    linkedList2Pointer = linkedList2.head

    if linkedList1Pointer is None:
        return linkedList2

    if linkedList2Pointer is None:
        return linkedList1

    concatLinkedList = LinkedList()
    concatLinkedListPointer = concatLinkedList.head

    while linkedList1Pointer != None and linkedList2Pointer != None:
        if linkedList1Pointer.data < linkedList2Pointer.data:
            #AttributeError: 'NoneType' object has no attribute 'next'
            if concatLinkedListPointer is None:
                concatLinkedListPointer = linkedList1Pointer
            else:
                concatLinkedListPointer.next = linkedList1Pointer
            linkedList1Pointer = linkedList1Pointer.next

        else:

            if concatLinkedListPointer is None:
                concatLinkedListPointer =  linkedList2Pointer
            else:
                concatLinkedListPointer.next = linkedList2Pointer
            linkedList2Pointer = linkedList2Pointer.next

        concatLinkedList.printLinkedList()


        concatLinkedListPointer = concatLinkedListPointer.next
    concatLinkedList.printLinkedList()

由于我的列表为空，并且我使用列表头本身指向了第一个元素，所以此代码块在那儿

if concatLinkedListPointer is None:
    concatLinkedListPointer = linkedList1Pointer

但是脚本可以无限期运行，但我不知道为什么。我似乎在这里正确地更改了下一个指针。

Answer 1

我不确定您合并是否会成功，首先，您要执行以下操作：

concatLinkedList = LinkedList()
concatLinkedListPointer = concatLinkedList.head

您将获得None，如果您对其进行更改，则concatLinkedList.head仍将指向None。简单的例子：

concatLinkedList = LinkedList()
concatLinkedListPointer = concatLinkedList.head
concatLinkedListPointer = Node(1)
print(concatLinkedList.head) # None

要修复它，您应该将新的concatLinkedList.head设置为Node，并在合并周期中稍后对其进行更新。

第二，例如，当第一个列表包含1个项目，第二个列表包含2个项目时，您的合并周期将不起作用。它将合并第一个列表中的项目，并在其后停止循环。我假设第一个列表包含最小的数字。