題目

給你鏈表的頭結(jié)點 head ，請將其按升序排列并返回排序后的鏈表。

例：
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]

方法一：自頂向下歸并排序

sort 函數(shù)：不斷將鏈表一分為二

• head 表示鏈表的頭結(jié)點，tail 表示鏈表的尾結(jié)點的下一個結(jié)點
• 若鏈表無結(jié)點，那么終止本次拆分鏈表
• 若鏈表只有一個結(jié)點，那么終止本次拆分鏈表，并將該結(jié)點的后繼結(jié)點設為空
• slow 和 fast 表示兩個指針，slow 每次走一步，fast 每次走兩步
• 循環(huán)直至快指針 fast 等于 tail
  • 快慢指針均后移一步，并判斷快指針此時是否位于 tail
    • 若并未走至鏈表結(jié)尾，那么繼續(xù)后移一步
• mid 表示鏈表的中間結(jié)點，根據(jù)上述快慢指針的移動，此時慢指針 slow 即位于中間結(jié)點，賦值
• 返回兩個鏈表繼續(xù)拆并分合并后新鏈表

merge 函數(shù)：根據(jù)每個結(jié)點值大小對兩個鏈表合并
思路同 21. 合并兩個有序鏈表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def sortList(self, head):
        def sort(head, tail):
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(sort(head, mid), sort(mid, tail))

        def merge(list1, list2):
            result = curr = ListNode()
            while list1 and list2:
                if list1.val <= list2.val:
                    curr.next = ListNode(list1.val)
                    list1 = list1.next
                else:
                    curr.next = ListNode(list2.val)
                    list2 = list2.next
                curr = curr.next
            if list1:
                curr.next = list1
            else:
                curr.next = list2
            return result.next

        return sort(head, None)

※
時間復雜度：O(nlogn)
空間復雜度：O(logn)

相關(guān)知識

• 歸并排序：
  

參考

代碼相關(guān)：https://leetcode.cn/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
歸并排序：https://www.cnblogs.com/chengxiao/p/6194356.html