python 解决 链表快排问题

Question

问题遇到的现象和发生背景

要求：创建quick_sort 函数只含有self,node两个parameter
用户输入的代码样式：

问题相关代码

我的解答思路和尝试过的方法

i左边的数小于pivot，i和j之间的包括ij都大于pivot

我想要达到的结果

从小到大输出链表

Answer 1

class Node:
    # 定义节点前驱，数据，后继
    def __init__(self, before=None, data=None, after=None):
        self.before = before
        self.data = data
        self.after = after


class LinkList:
    def __init__(self):
        # 前节点置空(不建议设置成None,因为前节点有一个指针域的)
        self.head = Node()

    # 清空链表
    def clear(self):
        self.head = Node()

    # 插入数据reverse=True时为从小到大排序,False为不排序
    def insert(self, data, reverse=False):
        p = self.head
        if p.data is None and p.after is None:
            p.after = Node(before=p, data=data)
            return None
        if reverse is True:
            self.sort(node=p.after, data=data)
        if reverse is False:
            self.create(node=p.after, data=data)

    # 从小到大递归插入
    def sort(self, node, data):
        while node.after is not None:
            if data <= node.data:
                new_node = Node(before=node.before, data=data, after=node)
                node.before.after = new_node
                node.before = new_node
                return None
            else:
                node = node.after
        if data < node.data:
            new_node = Node(before=node.before, data=data, after=node)
            node.before.after = new_node
            node.before = new_node
            return None
        new_node = Node(before=node, data=data)
        node.after = new_node
        return None

    # 正常插入
    def create(self, node, data):
        while node.after is not None:
            node = node.after
        new_node = Node(before=node, data=data)
        node.after = new_node

    # 显示链表的数据
    def display(self):
        p = self.head.after
        print('[', end='')
        while p.after is not None or p.data is not None:
            print(p.data, end='')
            if p.after is None:
                break
            p = p.after
            print(end=', ')
        print(']')


if __name__ == '__main__':
    n = [4, 2, 3, 1, 6, 0, -1, 1, 5]
    my_list0 = LinkList()
    my_list1 = LinkList()
    for i in range(len(n)):
        my_list0.insert(data=n[i], reverse=False)
        my_list1.insert(data=n[i], reverse=True)
    print("原列表:", n)
    print("无序插入链表:", end='')
    my_list0.display()
    print("有序插入链表:", end='')
    my_list1.display()

这个就是简单的数据结构的链表的实现，我即兴写的是双向链表的，双向链表的比较容易理解，
有很大的优化空间，时间复杂度和空间复杂度有点大，你可以修改一下，有用的话点一下采纳