用python解决排序链表问题
排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5
def quick_sort(li, start, end):
# 分治 一分为二
# start=end ,证明要处理的数据只有一个
# start>end ,证明右边没有数据
if start >= end:
return
# 定义两个游标，分别指向0和末尾位置
left = start
right = end
# 把0位置的数据，认为是中间值
mid = li[left]
while left < right:
# 让右边游标往左移动，目的是找到小于mid的值，放到left游标位置
while left < right and li[right] >= mid:
right -= 1
li[left] = li[right]
# 让左边游标往右移动，目的是找到大于mid的值，放到right游标位置
while left < right and li[left] < mid:
left += 1
li[right] = li[left]
# while结束后，把mid放到中间位置，left=right
li[left] = mid
# 递归处理左边的数据
quick_sort(li, start, left - 1)
# 递归处理右边的数据
quick_sort(li, left + 1, end)
if __name__ == '__main__':
l = [6, 5, 4, 3, 2, 1]
quick_sort(l, 0, len(l) - 1)
print(l)
# 稳定性：不稳定
# 最优时间复杂度：O(nlogn)
# 最坏时间复杂度：O(n^2)
这题很简单使用涉及简单的算法：堆排序。
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
概念示例图
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # 交换
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n, -1, -1):
heapify(arr, n, i)
# 一个个交换元素
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("排序后")
for i in range(n):
print ("%d" %arr[i]),
执行以上代码输出结果为：
排序后
5
6
7
11
12
13
```bash
```
class node(object):
def __init__(self,val,p = None):
self.val = val
self.next = p
def Linklist(a):
for i in range(len(a)):
a[i] = node(a[i])
for i in range(len(a)-1):
a[i].next = a[i+1]
return a
def sort(arr):
if arr is None or arr.next is None:
return arr
pre = arr
mid = arr
lon = arr
while lon and lon.next:
pre = mid
mid = mid.next
lon = lon.next.next
left,right = arr,mid
pre.next = None
return sortlink(sort(left),sort(right))
def sortlink(left,right):
pre = node(-1)
first = pre
while left and right:
if left.val > right.val:
pre.next = right
pre = right
right = right.next
else:
pre.next = left
pre = left
left = left.next
if left:
pre.next = left
else:
pre.next = right
return first.next
if __name__=='__main__':
a = [4,2,1,3]
Link = Linklist(a)
s = Link[0]
print('排序前：')
while s:
print(s.val)
s = s.next
b = sort(Link[0])
print('排序后：')
while b:
print(b.val)
b = b.next