假设有一带头结点的循环双链表表示的线性表L=(a
1
，a
2
，…，aa
n—1
，a
n
)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a
1
，a
3
，…，a
n
，…，a
4
，a
2
)。要求：
问答题
给出算法的基本设计思想。
【正确答案】正确答案：基本设计思想：从改造后的线性表L可以看出，前部分结点为奇序号结点，并且递增；后部分结点为偶序号结点，并且递减。所以可以考虑建立两个新的循环双链表，一个带头结点的循环双链表L（由原先的L改造而来），保存原先线性表L的奇数号结点，可以采取尾插法，让其序号顺序递增；而另外一个不带头结点的循环双链表s，保存原先线性表L的偶数号结点，可以采取头插法，让其序号顺序递减。最后，将L和s两个循环双链表连接成一个循环双链表L，并且L为其头结点指针。
【答案解析】
问答题
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
【正确答案】正确答案：算法实现如下： void modify(struct node *head) { struct node *s=NULL； struct notie *L=head； struct : nocie *p=L—＞next，*pl； L—＞next=L—＞prev NULL； for(；p !=L；p=pl) { if (p—＞next ! =L) { pl=p—＞next； p—＞next=p1—＞next； p1—＞next—＞prev=p； . //把偶数结点插入 s if {s==NULL) { s=p1； p1—＞next=p1—＞prev=p1； } else { p1—＞next=s； p1—＞prev=s—＞prev； s —＞prev—＞next=pl； s —＞prev=pl； s=s—＞prevr pl=p—＞next； L—＞prev—＞next=p； p—＞next=L； p—＞prev—L—＞prev； L—＞prev=p； if (s==NULL) return； p=s—＞prev p—＞next~L； L—＞prev—＞next=s ； s—＞prev=L—＞prev； L—＞prev=p；
【答案解析】
问答题
说明你所设计算法的时间复杂度与空间复杂度。
【正确答案】正确答案：空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。 时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。
【答案解析】