问答题假设有一带头结点的循环双链表表示的线性表L=(a₁，a₂，…，a_n-1，a_n)。
设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a₁，a₃，…，a_n，…，a₄，a₂)。要求：

问答题给出算法的基本设计思想。

【正确答案】基本设计思想：从改造后的线性表L可以看出，前部分结点为奇序号结点，并且递增；后部分结点为偶序号结点，并且递减。所以可以考虑建立两个新的循环双链表，一个带头结点的循环双链表L(由原先的L改造而来)，保存原先线性表L的奇数号结点，可以采取尾插法，让其序号顺序递增；而另外一个不带头结点的循环双链表S，保存原先线性表L的偶数号结点，可以采取头插法，让其序号顺序递减。最后，将L和S两个循环双链表连接成一个循环双链表L，并且L为其头结点指针。

【答案解析】

问答题根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

【正确答案】算法实现如下：
void modify(Struct node ^*head)
{
struct node ^*s=NULL;
struct node ^*L=head;
struct node ^*p=L-＞next,^*p1;
L-＞next=L-＞prev=NULL;
for(;P!=L;p=p1)
{
if(p-＞next !=L)
{
//删除偶数结点
p1=p-＞next;
P-＞next=p1-＞next;
p1-＞next-＞prey=P;
//把偶数结点插入s
if(s==NULL)
{
s=p1;
p1-＞next=p1-＞prev=p1;
} else
{
p1-＞next=s;
p1-＞prev=s-＞prey;
s-＞prev-＞next=p1;
s-＞prev=p1;
s=s-＞prev;
}
}
p1=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)。

【答案解析】