类型：链表
-
- 排序链表 💛 ⭐
https://leetcode-cn.com/problems/sort-list/
❓ 给定一个链表，将其升序排列后返回。
💡 插入排序
从前往后找插入点。
如果是数组的插入排序，则数组的前面部分是有序序列，后面的元素插入到前面后，插入位置后面的元素都往后移动一位。
对于链表来说，结点插入不需要挨个地挪位置，因此插入的时间复杂度是 O(1)，但是每查找一个插入位置都需要 O(n)，所以总的时间复杂度仍然达到了 O(n^2)。
由于单向链表只有指向后一结点的指针，因此我们从前往后地进行插入。同时我们在头部建立虚拟头结点，以方便在头结点之前插入结点。
class Solution: def insertionSortList(self, head: ListNode) -> ListNode: if not head: return head dummyHead = ListNode(0) dummyHead.next = head lastSorted = head curr = head.next while curr: if lastSorted.val <= curr.val: lastSorted = lastSorted.next else: prev = dummyHead while prev.next.val <= curr.val: prev = prev.next lastSorted.next = curr.next curr.next = prev.next prev.next = curr curr = lastSorted.next return dummyHead.next时间复杂度：O(n^2)，空间复杂度：O(1)
💡 归并排序（自顶向下）
过程如下：
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。可以使用快慢指针。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并。
class Solution: def sortList(self, head: ListNode) -> ListNode: def sortFunc(head: ListNode, tail: ListNode) -> ListNode: 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(sortFunc(head, mid), sortFunc(mid, tail)) def merge(head1: ListNode, head2: ListNode) -> ListNode: dummyHead = ListNode(0) temp, temp1, temp2 = dummyHead, head1, head2 while temp1 and temp2: if temp1.val <= temp2.val: temp.next = temp1 temp1 = temp1.next else: temp.next = temp2 temp2 = temp2.next temp = temp.next if temp1: temp.next = temp1 elif temp2: temp.next = temp2 return dummyHead.next return sortFunc(head, None)时间复杂度：O(NlogN)，空间复杂度：O(logN)
💡 归并排序（自底向上）
先计算链表长度 length。
然后
- 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。
- 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。
- 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。
class Solution: def sortList(self, head: ListNode) -> ListNode: def merge(head1: ListNode, head2: ListNode) -> ListNode: dummyHead = ListNode(0) temp, temp1, temp2 = dummyHead, head1, head2 while temp1 and temp2: if temp1.val <= temp2.val: temp.next = temp1 temp1 = temp1.next else: temp.next = temp2 temp2 = temp2.next temp = temp.next if temp1: temp.next = temp1 elif temp2: temp.next = temp2 return dummyHead.next if not head: return head length = 0 node = head while node: length += 1 node = node.next dummyHead = ListNode(0, head) subLength = 1 while subLength < length: prev, curr = dummyHead, dummyHead.next while curr: head1 = curr for i in range(1, subLength): if curr.next: curr = curr.next else: break head2 = curr.next curr.next = None curr = head2 for i in range(1, subLength): if curr and curr.next: curr = curr.next else: break succ = None if curr: succ = curr.next curr.next = None merged = merge(head1, head2) prev.next = merged while prev.next: prev = prev.next curr = succ subLength <<= 1 return dummyHead.next时间复杂度：O(NlogN)，空间复杂度：O(1)