问答题
设有带头结点的循环双链表表示的线性表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;
}
【答案解析】
问答题
说明你所设计算法的时间复杂度和空间复杂度。
【正确答案】说明算法的复杂性：上述算法的时间复杂度为O(n)，算法的空间复杂度为O(1)。
【答案解析】[解析] 用p指针扫描L的所有结点，先将L构造为只有一个带头结点的循环双链表，而用指针s构造不带头结点的循环双链表(初始时为NULL)，对于奇数序号的结点*p，采用尾插法插入到L中，对于偶数序号的结点*p，采用头插法插入到S中。最后将L和S两个循环双链表连接成一个循环双链表，L为其头结点指针。