鏈表快排

給定一個單向鏈表，在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()