题目:设以带头结点的双向循环链表表示的线性表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)