LeetCode 148. 排序链表

题目

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

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

方法一：自顶向下归并排序

sort 函数：不断将链表一分为二

• head 表示链表的头结点，tail 表示链表的尾结点的下一个结点
• 若链表无结点，那么终止本次拆分链表
• 若链表只有一个结点，那么终止本次拆分链表，并将该结点的后继结点设为空
• slow 和 fast 表示两个指针，slow 每次走一步，fast 每次走两步
• 循环直至快指针 fast 等于 tail
  • 快慢指针均后移一步，并判断快指针此时是否位于 tail
    • 若并未走至链表结尾，那么继续后移一步
• mid 表示链表的中间结点，根据上述快慢指针的移动，此时慢指针 slow 即位于中间结点，赋值
• 返回两个链表继续拆并分合并后新链表

merge 函数：根据每个结点值大小对两个链表合并
思路同 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)

相关知识

• 归并排序：
  

参考

代码相关：https://leetcode.cn/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
归并排序：https://www.cnblogs.com/chengxiao/p/6194356.html