设以带头结点的双向循环链表表示的线性表L=a1,a2,a3...an。试写一时间复杂度O(n)的算法,将L改造为L=a1,a3,...an,...a4,a2。
void Reform(DuLinkedList &L)//按1,3,5,...4,2 的顺序重排双向循环链表 L中的所有结点 { p=L.next; while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; } //此时 p 指向最后一个奇数结点 if(p->next==L) p->next=L->pre->pre; else p->next=l->pre; p=p->next; //此时 p 指向最后一个偶数结点 while(p->pre->pre!=L) { p->next=p->pre->pre; p=p->next; } p->next=L; //按题目要求调整了 next链的结构,此时 pre 链仍为原状 for(p=L;p->next!=L;p=p->next) p->next->pre=p; L->pre=p; //调整 pre 链的结构,同 2.32方法 }
分析:next 链和 pre 链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.