C语言代码【问题描述】: 设线性表L = (a1 ,a2，a3，.…，an-1，an）采用带头结点的单链表保存，请设计一个空间复杂度为 0(1）且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表S＝ (a1，an，a2，an-1，.…）。 【输入形式】：多组数据，每组第一行为n，表示链表的长度。接下来为链表中的元素。不超过5组数据。 【输出形式】：每组数据，输出重新排列后的序列。 【样例输入】 10 11 13 15 17 19 2 4 6 8 20 【样例输出】 11 20 13 8 15 6 17 4 19 2

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int data;
struct Node* next;
}Node, *List;

List createList(int n) { // 创建链表
List L = (List)malloc(sizeof(Node));
L->next = NULL;
Node* tail = L;
for (int i = 0; i < n; i++) {
Node* p = (Node*)malloc(sizeof(Node));
scanf("%d", &p->data);
p->next = NULL;
tail->next = p;
tail = p;
}
return L;
}

void reverse(List L) { // 反转链表
Node* p = L->next;
L->next = NULL;
while (p) {
Node* tmp = p->next;
p->next = L->next;
L->next = p;
p = tmp;
}
}

void merge(List L) { // 合并链表
Node* p = L->next;
Node* q = p->next;
while (q && q->next) {
Node* tmp = q->next;
q->next = p->next;
p->next = q;
p = q->next;
q = tmp;
}
if (q) { // 如果链表长度为奇数，将最后一个结点插入到中间
q->next = p->next;
p->next = q;
}
}

void printList(List L) { // 输出链表
Node* p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

int main() {
int n;
while (scanf("%d", &n) != EOF) {
List L = createList(n);
reverse(L); // 反转链表
merge(L); // 合并链表
printList(L); // 输出链表
}
return 0;
}