将一个链表前后交替插入，得到一个新链表

设线性表 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,…) 。

方法一：

思想：将链表平均分成两个链表A，B。假设A当前指向ai，把B表尾插入到ai后面，A表重新指向性的ai（L1=L1->next->next）。

void dividList(NODE *L,NODE *L2){NODE *slow=L,*fast=L;while(fast!-NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}L2=slow->next;slow->next=NULL;
}
void change_list(NODE *L){NODE *L2;dividList(L,L2);//指向L的第一个结点 NODE *L1=L->next;//将L2尾结点依次间隔插入到L1中 while(L2!=NULL){//找最后一个尾结点 NODE *p=L2,*q=NULL;while(p->next!=NULL){//记录 p的前驱 q=p;p=p->next;}if(q != NULL){//摘下p结点 q->next=NULL;}L2=NULL;}//插入到L1 p->next=L1->next;//间隔一位 L1=L1->next->next;}

时间复杂度O（n^2）；空间复杂度O（1）

方法二：

代码：

思想：将链表平均分成两个链表A，B。对B表进行逆转，每次取A，B表中一个元素，尾插到C表中，先插A，再插入B。直到A和B表为空。

//将链表平均分成两个链表 
void dividList(NODE *L,NODE *L2){NODE *slow=L,*fast=L;while(fast!-NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}L2=slow->next;slow->next=NULL;
}
//逆转无头结点的单链表L 
void reverseList(NODE *L){//额外申请一个头结点 NODE *head=(NODE*)malloc(sizeof(NODE));head->next=NULL;NODE *s;//取下结点进行头插 while(L!=NULL){s=L->next;L->next=head->next;head->next=L;L=s;}//去掉头结点 L=head->next;free(head); 
}
void change_list(NODE *L){NODE *L2,L1;//索引两个表 NODE *tail;//指向新表尾结点 NODE *p,*q;//辅助变量 dividList(L,L2);//去掉头节点 L1=L->next;L->next=NULL;//指向新表尾结点 tail=L;reverseList(L2);//交替插入到L while(L1!=NULL&& L2!=NULL){p=L1->next;q=L2->next;//尾插L1 tail->next=L1;tail=L1;//尾插L12tail->next=L2;tail=L2;//向后移动，进行遍历 L1=p;L2=q;}//L1中可能还有剩余值(链表为奇数个时) if(L1!=NULL){tail->next=L1;tail=tail->next;}//尾巴置空 tail->next=NULL;
}

时间复杂度O（n）；空间复杂度O（1）