4.22排序链表（几种排序算法比较）
我一开始的思路是，用快慢指针，采用冒泡排序的思想，先两两比较，再循环n-1轮。但这个方法复杂度高，而且还需要另外定义一个基准指针用来存放每次循环的开头。
复习了一下所有排序算法的思路：
| 算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 最坏时间复杂度的情况 | 介绍 |
| 冒泡排序 | O(N) | O(N²) | 输入数组完全逆序 | 多次交换相邻元素将最大值“冒泡”到末尾 |
| 选择排序 | O(N) | O(N²) | 直接选择（从0开始逐一比较，再从1往后递推。） | |
| O(Nlog2N) | O(Nlog2N) | 堆排序 | ||
| 插入排序 | O(N) | O(N²) | 输入数组完全逆序 | 直接插入,希尔排序 |
| 快速排序 | O(Nlog2N) | O(N²) | 分区极度不平衡 | 左边第一个数叫做基准数，左指针找到比基准数大的停住，右指针找到小的停住，然后俩指针交换数字但位置不变，继续找直到相遇，将该位置数字与基准数交换，再左右分别看成一个序列排序。 |
| 归并排序 | O(Nlog2N) | O(Nlog2N) | 将大问题递归分成很多个小问题，进行排序，然后递归合并 |
结合题解，决定还是采用归并算法比较稳定并快捷一点。
归并算法的整体思路是，先将链表一分为2， 然后递归继续分开，直到分成最小单位不能再分开位置，然后开始递归合并，合并的方式是先将left,right指针分别放在两个最小单位的开头，然后比较值的大小，小的直接跟在h（结果链表，一开始是一个0值节点）的后面，然后小的那部分指针往后面移动，继续比较left,right指针对应值的的大小，然后比较完成返回，（这时最小单位已经排序完成）递归到倒数第二层继续比较然后合并。
class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null) return head;ListNode slow = head;ListNode fast = head.next;//找到中点while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;}ListNode tmp = slow.next;slow.next = null;//递归分开ListNode left = sortList(head);ListNode right = sortList(tmp);ListNode h = new ListNode(0);ListNode res = h;while(left!=null && right!=null){if(left.val < right.val){h.next = left;left = left.next;}else{h.next = right;right = right.next;}h = h.next;}h.next = left!=null?left:right;return res.next;//一开始res是0所以要返回next}
}以上代码来自于 148. 排序链表 - 力扣（LeetCode）