数据结构
2019-41
设线性表 L=(a1,a2,a3,…,an-2,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）说明所设计算法的时间复杂度。
答案
（1）先用快、慢指针找到链表中点，再原地逆置后半段，最后将前半段和逆置后的后半段交替合并。
（2）一种实现如下：
void reorderList(node *h) {
node *p, *q, *r, *s;
p = q = h;
while(q->next != NULL) { // 找到中间结点
p = p->next;
q = q->next;
if(q->next != NULL) {
q = q->next;
}
}
q = p->next;
p->next = NULL;
while(q != NULL) { // 后半部分原地逆置
r = q->next;
q->next = p->next;
p->next = q;
q = r;
}
s = h->next;
q = p->next;
p->next = NULL;
while(q != NULL) { // 逐个插入结点
r = q->next;
q->next = s->next;
s->next = q;
s = q->next;
q = r;
}
}（3）时间复杂度为 O(n)，空间复杂度为 O(1)。函数名与参数按测试文档统一为 reorderList(node *h)。