1.4 如何对链表进行重新排序

【出自WR笔试题】

难度系数：★★★☆☆

被考察系数：★★★★☆

题目描述：

给定链表L0→L1→L2→…→Ln-1→Ln，把链表重新排序为L0→Ln→L1→Ln-1→L2→Ln-2→…。要求：①在原来链表的基础上进行排序，即不能申请新的结点；②只能修改结点的next域，不能修改数据域。

分析与解答：

主要思路为：

1）首先找到链表的中间结点。

2）对链表的后半部分子链表进行逆序。

3）把链表的前半部分子链表与逆序后的后半部分子链表进行合并，合并的思路为：分别从两个链表各取一个结点进行合并。实现方法如下图所示。

实现代码如下：

程序的运行结果为

算法性能分析：

查找链表的中间结点的方法的时间复杂度为O（N），逆序子链表的时间复杂度也为O（N），合并两个子链表的时间复杂度也为O（N）。因此，整个方法的时间复杂度为O（N），其中，N表示链表的长度。由于这种方法只用了常数个额外指针变量，因此，空间复杂度为O（1）。

引申：如何查找链表的中间结点

分析与解答：

主要思路：用两个指针从链表的第一个结点开始同时遍历结点，一个快指针每次走两步，另外一个慢指针每次走一步；当快指针先到链表尾部时，慢指针则恰好到达链表中部（快指针到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针，当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点）。上面的代码FindMiddleNode就是用来求链表的中间结点的。