对 Python 中的链接列表进行排序

Question

我很难整理链表。我正在考虑剥离列表中的每个项目并将每个项目附加到新列表并按顺序添加。但我想在列表中对它们进行排序。我按逻辑想出来了，画出来了，但是好像不行哈哈。为了简单起见，我删除了很多我的代码，剩下的代码因为它们不需要。

class Node:

    def __init__(self, initdata, position = 0):

        self.data = initdata
        self.next = None
        self.position = position

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newdata):
        self.data = newdata

    def setNext(self, newnext):

        self.next = newnext

    def __str__(self):
        return str(self.data)

class LinkedList:

    def __init__(self):

        self.head = None
        self.tail = None

    def sortList(self):

        previous = self.head
        current = previous.getNext() # Earth
        temp = current.getNext() #Venus
        stop = False
        while current != None: #None
            if current.getData() > temp.getData():
                previous.setNext(temp)
                temp.setNext(current)
                current.setNext(temp.getNext())
                previus = current
                current = temp
                temp = temp.getNext()
            else:
                previous = current
                current = temp
                temp = temp.getNext()

所以链表如下，头部为地球

[Earth] points to [Venus] points to [Mercury] points to None

我要

[Earth] points to [Mercury] points to [Venus] points to None

到目前为止，经过多次试验，我还没有得到这个结果:(有帮助吗？

Answer 1

交换节点时，交换相邻节点最终会旋转 3 个 next 指针，而交换非相邻节点会交换 2 对 next 指针。这两种情况都可以通过在要交换的节点之前交换节点的下一个指针，然后按顺序交换要交换的节点的下一个指针来处理。

代码还需要处理节点是列表的第一个节点（在这种情况下更新头指针）和节点是列表的最后一个节点（在这种情况下尾部指针）的情况指针已更新）。

你提到的第一种方法，从原始列表中删除节点，然后按顺序将它们插入到最初为空的列表中，应该更容易、更快捷。

最快的方法是使用头指针数组（大小为 26 到 32），这些头指针要么为 NULL，要么指向大小为 2^i（2 的 i 次方）的列表。该算法使用一个基本的合并列表函数来合并两个已经排序的列表。节点一次插入一个数组。然后合并数组，形成最终的排序数组。这是 C++ std::list:sort() 使用的方法（至少对于 HP / Microsoft STL）。

对 Python 中的链接列表进行排序

Sorting a Linked List in Python

sorting

linked-list

python-3.x