python实现链表重新排序问题

Question

已经实现链表的数据结构和一些基本功能如求长度、插入新的数值等，现要对一个链表中的数字进行
排序，如（1,2,3,4,5)排序后成为(3,2,4,1,5),即以原来链表中第(length/2)个节点作为head，往后依次是原节点左1、右1、左2、右2...类推，求解如何不改变各个节点的地址实现排序。

Answer 1

这个就是二叉树排序算法

def binaryTreeSort(l):
    assert(type(l)==type(['']))
    length = len(l)
    if length==0 or length==1:
        return l
    class Node:
        def __init__(self,value=None,left=None,right=None):
            self.__value = value
            self.__left = left
            self.__right = right
        @property
        def value(self):
            return self.__value
        @property
        def left(self):
            return self.__left
        @property
        def right(self):
            return self.__right

    class BinaryTree:
        def __init__(self,root=None):
            self.__root = root
            self.__ret=[]

        @property
        def result(self):
            return self.__ret
        def add(self,parent,node):
            if parent.value>node.value:
                if not parent.left:
                    parent.left = node
                else:
                    self.add(parent.left,node)
                pass
            else:
                if not parent.right:
                    parent.right = node
                else:
                    self.add(parent.right,node)

        def Add(self,node):
            if not self.__root:
                self.__root = node
            else:
                self.add(self.__root, node)

        def show(self,node):
            if not node:
                return
            if node.right:
                self.show(node.right)
            self.__ret.append(node.value)
            if node.left:
                self.show(node.left)

        def Show(self):
            self.show(self.__root)

    b = BinaryTree()
    for i in l:
        b.Add(Node(i))
    b.Show()
return b.result