问题
问答题
设有带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a3，…，an，…，a4，a2)。要求：
说明你所设计算法的时间复杂度和空间复杂度。
答案
参考答案：说明算法的复杂性：上述算法的时间复杂度为O(n)，算法的空间复杂度为O(1)。
解析： 用p指针扫描L的所有结点，先将L构造为只有一个带头结点的循环双链表，而用指针s构造不带头结点的循环双链表(初始时为NULL)，对于奇数序号的结点*p，采用尾插法插入到L中，对于偶数序号的结点*p，采用头插法插入到S中。最后将L和S两个循环双链表连接成一个循环双链表，L为其头结点指针。