题目
给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。
例：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
方法一：自顶向下归并排序
sort 函数：不断将链表一分为二
- head 表示链表的头结点，tail 表示链表的尾结点的下一个结点
- 若链表无结点，那么终止本次拆分链表
- 若链表只有一个结点，那么终止本次拆分链表，并将该结点的后继结点设为空
- slow 和 fast 表示两个指针，slow 每次走一步，fast 每次走两步
- 循环直至快指针 fast 等于 tail
- 快慢指针均后移一步，并判断快指针此时是否位于 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
