设有带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a3，…，an，…，a4，a2)。要求：
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
参考答案：用C语言算法描述如下：
void split (DLinkList &L){
DLinkList *p=L-＞next, *q, *s=NULL;
L-＞next=L; L-＞prior=L; //构造只有一个头结点的循环双链表
while(p!=L){ //扫描L的所有结点
q=p-＞next;
p-＞next=L; p-＞prior=L-＞prior; //将*p结点插入到L循环双链表的末尾
L-＞prior-＞next=p; L-＞prior=p;
p=q; q=p-＞next;
if(s=NULL) { //s原为空表时，现只含有一个结点
s=p;
s-＞next=s; s-＞prior=s;
}
else { //将*p插入到s的前端
p-＞next=s; p-＞prior=s-＞prior;
s-＞prior-＞next=p;s-＞prior=p;
s=p;
}
p=q;
}
s-＞prior-＞next=L; //将L和s合并起来
L-＞prior-＞next=s;
q=L-＞prior;
L-＞prior=s-＞prior;
s-＞prior=q;
}