[数据结构与算法]线性表重排

设线性表 L= ( a1 ， a2 ， a… ， an-2 ， a-1 ， a 。 ) 采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node {
int data ；
struct node* next ；
} NODE ；
请设计一个空间复杂度为 O ( 1 ) 且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L’= ( a 1 ， a n ， a 2 ， a n-1 ， a 3 ， a n-2 … ) 。

本题综合链表逆置、双指针（也可以理解为快慢指针）

//时间复杂度O（n），空间复杂度O（n）
void change_list(Node *h){
Node *p,*q,*r,*s;
p=q=h;//先开始都是从表头开始
while(q->next!=NULL)//寻找中间结点
    p=p->next;//p走一步
    q=q->next;
    if(q->next!=NULL)//使q走两步 利用步长来控制长度的比
        q=q->next;
}
q=p->next;//使q指向中间结点
p->next=NULL;//相当于就地逆置的另一个指针
while(q!=NULL){//将链表后半段逆置
    r=q->next;//r暂存q的下一个指针节点
    q->next=p->next;
    p->next=q;
    q=r;
}
s=h->next;//前半段的第一个结点
q=p->next;//指向后半段的第一个结点
p->next=NULL;
while(q!=NULL){//开始将链表插入
    r=q->next;
    p->next=s->next;
    s->next=q;
    s=q->next;
    q=r;
}
}