给定一个单向链表，在O(1)空间复杂度和O(nlogn)时间复杂度下进行排序

# -*- coding: utf-8 -*-# @Time : 2019-04-19 20:07# @Author : Jayce Wong# @ProjectName : job# @FileName : linkedListQuickSort.py# @Blog : https://blog.51cto.com/jayce1111# @Github : https://github.com/SysuJayce# Definition for singly-linked list.class ListNode: def __init__(self, x): self.val = x self.next = Nonedef linkedListQuickSort(head): sort_helper(head, None) return headdef sort_helper(head, end): """ 快排本质上来讲就是选择一个主元，比主元小的值都放到主元左边(以升序为例)，其他都放到右边 因此不论是数组还是链表，快排的递归代码是一样的 """ # 由于我们这里判断了head是否和end相等来作为递归的出口，因此不必向数组那样判断下标起止点的大小 # 来作为递归出口 if head != end: pivot = quick_sort(head) sort_helper(head, pivot) sort_helper(pivot.next, end)def quick_sort(head): # 由于在链表中我们不能像数组那样选择一个下标来作为主元位置，因此就选择待排序链表的第一个元素作 # 为主元即可。 fast, slow = head.next, head # slow是用来标记比主元小的元素应在的位置，fast用来遍历 while fast: # 当发现有元素比主元(head)的值小的时候，我们先确定这个元素应该在的节点，然后将当前节点 # 的值和应该在的节点的值交换 if fast.val < head.val: slow = slow.next slow.val, fast.val = fast.val, slow.val fast = fast.next # 最后将主元的值放到正确的节点上 slow.val, head.val = head.val, slow.val # 返回主元所在的节点 return slowdef main(): head = ListNode(3) head.next = ListNode(4) head.next.next = ListNode(2) head.next.next.next = ListNode(5) head = linkedListQuickSort(head) while head: print(head.val) head = head.nextif __name__ == '__main__': main()