题目描述（中等难度）

要求时间复杂度为 ，最常用的就是归并排序了。

解法一

归并排序需要一个辅助方法，也就是对两个有序链表进行合并，在 已经讨论过。

至于归并排序的思想，这里就不多讲了，本科的时候用 Scratch 做过一个演示视频，感兴趣的可以参考 这里，哈哈。

那就直接放代码了。因为归并排序是一半一半的进行，所以需要找到中点。最常用的方法就是快慢指针去找中点了。

如果 和 fast 都从 head 开始走，那么当 fast 结束的时候， 就会走到后边一半节点的开头了。

当然除了上边的方法，在 看到，还可以加一个 pre 指针，让它一直指向 slow 的前一个即可。

他们的目的都是一样的，就是为了方便的把两个链表平均分开。

当然严格的说，上边的解法空间复杂度并不是 O(1)，因为递归过程中压栈是需要消耗空间的，每次取一半，所以空间复杂度是 。

总

和 一样，主要还是考察对链表的理解和排序算法的实现。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^