问答题
4. 给定链表L0-＞L1-＞L2…-Ln-1＞Ln，把链表重新排序为L0-＞Ln-＞L1-＞Ln-1＞L2-＞Ln-2…。要求：(1)在原来链表的基础上进行排序，即不能申请新的结点；(2)只能修改结点的next域，不能修改数据域。
【正确答案】主要思路为：(1)首先找到链表的中间结点；(2)对链表的后半部分子链表进行逆序；
(3)把链表的前半部分子链表与逆序后的后半部分子链表进行合并，合并的思路为：分别从两个链表各取一个结点进行合并。实现方法如下图所示：
(3)把链表的前半部分子链表与逆序后的后半部分子链表进行合并，合并的思路为：分别从两个链表各取一个结点进行合并。实现方法如下图所示：
【答案解析】
[考点] 如何对链表进行重新排序。