第 41 题
设线性表L=(a1 ,a2 ,a3 ,⋯,an−1 ,an−1 ,an )采用带头结点的单链表保存，链表中的结点定义如下：
typedef struct node {
int data;
struct node *next;
} NODE;
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L′=(a1 ,an ,a2 ,an−1 ,a3 ,an−2 ,⋯)。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度。
[tag_link]
1）算法的基本设计思想：先观察 L(a1 ,a2 ,a3 ,⋯,an−2 ,an−1 ,an) 和 L’(a1 ,an ,a2 ,an−1 ,a3 ,an−2 ,⋯)，发现 L’ 是由 L 摘取第一个元素，再摘取倒数第一个元素⋯依次合并而成的。为了方便链表后半段取元素，需要先将 L 后半段原地逆置［题目要求空间复杂度为 助栈］，否则每取最后一个结点都需要遍历一次链表。①先找出链表 L 的中间结点，为此设置两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正好在链表的中间结点；②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。
2）算法实现如下：
// 找到链表的中间结点
NODE *findMiddleNode(NODE *head) {
NODE *slow = head;
NODE *fast = head;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
fast = fast->next;
}
slow = slow->next;
}
return slow;
}
// 反转链表
NODE *reverse(NODE *start) {
NODE *p = start;
NODE *q = start->next;
while (q != NULL) {
NODE *tmp = q->next;
q->next = p;
p = q;
q = tmp;
}
return p;
}
// 1. 找到中位结点
// 2. 翻转后一半链表
// 3. 遍历两个链表，依次穿插所有结点
void solve(HEAD *head) {
if (head->next == NULL) {
return;
}
NODE *middle = findMiddleNode(head);
NODE *list2 = reverse(middle);
NODE *list1 = head->next;
// 穿插操作
NODE *p = list1;
NODE *q = list2;
// 退出循环的条件
// 链表长度为奇数：p == q
// 链表长度为偶数：p->next == q
// while (!(p == q || p->next == q))
while (p != q && p->next != q) {
NODE *tmp1 = p->next;
NODE *tmp2 = q->next;
p->next = q;
q->next = tmp1;
p = tmp1;
q = tmp2;
}
}
3）第 1 步找中间结点的时间复杂度为 O(n)，第 2 步逆置的时间复杂度为 O(n)，第 3 步合并链表的时间复杂度为 O(n)，所以该算法的时间复杂度为 O(n)。