（1）算法的基本设计思想∶先观察L（a1，a2，a3，……，an-2，an-1，an）和L'（a1，an，a2，an-1，a3，an-2，……），发现L'是由L摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素，需要先将L后半段原地逆置 【题目要求空间复杂度为O（1），不能借助栈】，否则每取最后一个结点都需要遍历一次链表。①先找出链表L的中间结点，为此设置两个指针p和q，指针p 每次走一步，指针g每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点;②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。
（2）算法实现∶
void change_list(NODE *h){
NODE *p,*q,*r,*s;
p=q=h;
while（q->next!=NULL）{ // 寻找中间结点
D=p->next;//p 走一步
q=q->next;
if（q->next!=NULL） q=q->next;//q 走两步
}
q=p->next;//p 所指结点为中间结点， q 为后半段链表的首结点
p->next=NULL;
while（q!=NULL）{ //将链表后半段逆置
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
s=h->next;//s 指向前半段的第一个数据结点，即插入点
q=p->next;//q 指向后半段的第一个数据结点
p->next=NULL;
while（q!=NULL）{ //将链表后半段的结点插入到指定位置
r=q->next;//r 指向后半段的下一个结点
q->next=S->next;//将q 所指结点插入到s 所指结点之后
S->next=q;
S=q->next;//s 指向前半段的下一个插入点
q=r;
}
}
（3）第1步找中间结点的时间复杂度为O（n），第 2步逆置的时间复杂度为 O（n），第3步合并链表的时间复杂度为 O（n），所以该算法的时间复杂度为 O（n）。