189 8069 5689
给定一个单向链表，在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 = None
def linkedListQuickSort(head):
sort_helper(head, None)
return head
def 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 slow
def 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.next
if __name__ == '__main__':
main()另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。