综合题
设线性表 L=(a1，a2，a…，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node {
int data；
struct node* next；
} NODE；
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L'=(a1，an，a2，an-1，a3，an-2…)。
要求：
问答题
给出算法的基本设计思想。
【正确答案】
算法的基本设计思想：
先观察L=（a1，a2，a3，...，an-1,an）和 L'=（a1，an，a2，an-1，a3，an-2，...），发现 L'是由 L 摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素，需要先将 L 后半段原地逆置［题目要求空间复杂度为 O(1)，不能借助栈］，否则每取最后一个结点都需要遍历一次链表。①先找出链表 L 的中间结点，为此设置两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正好在链表的中间结点；②然后将L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。
【答案解析】
问答题
根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
【正确答案】
算法实现：
【答案解析】
问答题
说明你所设计的算法的时间复杂度。
【正确答案】
第1步找中间结点的时间复杂度为O(n)，第2步逆置的时间复杂度为O(n)，第3步合并链表的时间复杂度为0(n)，所以该算法的时间复杂度为O(n)。
【答案解析】