【算法】leetcode热题--148.排序链表
https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked
问题
需要对于链表进行排序，需要空间复杂度为O1， 时间复杂度为Ologn
思路
先考虑时间复杂度，能够实现Ologn的算法就已经没几个了
- 快排
- 堆排
- 归并
快排
首先考虑一下快排。
简单的算法过程是，选中一个点，让其找到最终的排序点位，让左边的都比其小，让右边都比其大。然后让左右两边依次进行递归操作。
正常都是直接选取最左边的点。选定之后，就需要按照算法找到他最终的位置。
问题来了，算法需要通过从向左向右，然后假设出现情况，需要从右向左。链表从左向右没问题，但是从右向左就有问题了。又不是双向链表。
如果需要实现从右向左，需要新开辟一个指针数组，那么这不符合空间复杂度为O1的情况
堆排
这个没什么好说的，这个在数组实现是需要能够做到随机读取的，链表显然做不到。直接pass
归并
归并一开始我认为是并不可以的。因为在正常数组排序之中，他有空间复杂度的开销，一般认为是On 因为在归并的过程之中需要开辟一个新的数组存放。
但在链表之中刚好是不需要这部分开销的。因为在归并构造新的链表时候，只需要将目标结点移动到新的链表尾端即可，这样就没有额外内存开销。这样可以使得归并排序在链表的空间复杂度为O1并且，最后判断两个链表时候，只需要将其与目标链表链接在一起就可以了，而不需要重复循环移动每一个结点
此外归并排序有两种方法，自顶向下与自底向上
一般来说是写自顶向下的，因为这样写法可以直接用递归来写，比较好写代码。但涉及了递归，就不要忘记了递归会产生额外的栈空间的消耗，所以使用自顶向下的归并其实还是有额外空间消耗，即Ologn。所以上文中提及的快排其实也是不行的，也会有栈空闲消耗。
自底向上归并主要想法其实就是与自顶向下相反。
自顶向下就是整个数组先拆两个数组归并，然后两个数组拆成四个数组以此类推。直到我的数组只剩下一个单位，就跟他拆分的那个数组进行归并。
自底向上就是先定下一个subLength表示每一个小数组单元的数值（初始值必定为1）。然后按照这个数值进行分组，两两进行归并。
所以大体的循环框架就出来了：
- 针对subLength进行循环，直到subLength超过链表长度为止
- 针对subLength对链表进行分组，然后每两个进行归并操作，直到每一个组别都完成
第一个循环比较好想，第二个循环就比较复杂。
问题1:循环怎么控制？通过什么东西控制？
可以通过一个cur指针进行控制，假设说cur指针为nil就说明已经指向尾部，不需要再进行额外操作。
问题2：怎么进行两个链表裁切工作？
利用当前subLength进行计数裁切就可以了。
问题3:merge完链表插入到哪里？
可以直接开辟一个链表，排序完直接往后面插入就可以了。
// merge两个链表
func merge(head1, head2 *ListNode) *ListNode {dummyHead := &ListNode{}temp, temp1, temp2 := dummyHead, head1, head2for temp1 != nil && temp2 != nil {if temp1.Val <= temp2.Val {temp.Next = temp1temp1 = temp1.Next} else {temp.Next = temp2temp2 = temp2.Next}temp = temp.Next}// 只要判断一下，然后接入最终的链表就好了，不需要循环复制if temp1 != nil {temp.Next = temp1} else if temp2 != nil {temp.Next = temp2}return dummyHead.Next
}func sortList(head *ListNode) *ListNode {if head == nil {return head}length := 0for node := head; node != nil; node = node.Next {length++}dummyHead := &ListNode{Next: head}for subLength := 1; subLength < length; subLength <<= 1 {prev, cur := dummyHead, dummyHead.Nextfor cur != nil {head1 := curfor i := 1; i < subLength && cur.Next != nil; i++ {cur = cur.Next}head2 := cur.Nextcur.Next = nilcur = head2for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {cur = cur.Next}var next *ListNodeif cur != nil {next = cur.Nextcur.Next = nil}prev.Next = merge(head1, head2)for prev.Next != nil {prev = prev.Next}cur = next}}return dummyHead.Next
}