归并排序介绍

其基本思想是分治，

步骤如下：

1. 找分界点，将要排序的序列分为两部分。
2. 递归处理左右两个子序列。
3. 归并，将两个有序的序列合并成一个。

归并排序是一种时间复杂度为 O(n log n ) 的排序方法，与快排相比较，其需要一个额外的空间。

应用

148. 排序链表

23. 合并K个升序链表

1. 先找出中间节点，然后再从中间节点处将链表断开，找中间节点可以看这题 876. 链表的中间结点
2. 使用归并排序，先递归处理左右两个子链表，然后对其进行归并处理

143. 重排链表

这题根据重新排序的链表顺序，可以先将链表分为前后两个部分，然后将后半部分先反转（206. 反转链表），将反转后的两部分链表合并即可，不过这里的合并必须在原链表上进行，所以不能新建空头了再处理了。