循环双链表,将L改造为L=(a1,a3,…,an,a4,a2)
题目:设以带头结点的双向循环链表表示的线性表L=(a1,a2,…..,an).试写出一时间复杂度为o(n)的算法,将L改造为L=(a1,a3,…,an,a4,a2)
思想:将偶数头插到表尾,奇数顺序保持不变。
代码:
void change(DListNode &L){
//q指向循环双链表的最后一个结点
DListNoode *p=L->next,*q=L->pre,*r;
int i=1;
while(p!=q){
if(i%2==0){
r=p;
p=p->next;
r->pre->next=r->next;
r->next->pre=r->pre;
//将偶数头插到后面
r->pre=q;
q->next->pre=r;
r->next=q->next;
q->next=r;
}else{
p=p->next;
}
i++;
}
}
时间复杂度O(n),空间复杂度O(1)