在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个下一个指针，而交换非相邻节点会交换2对下一个指示器。这两种情况都可以通过在要交换的节点之前交换节点的下一个指针来处理，然后按该顺序交换要交换的结点的下一指针。

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

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

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