list 的翻转reverse源码：
// 将链表倒置 // 其算法核心是历遍链表, 每次取出一个结点, 并插入到链表起始点 // 历遍完成后链表满足倒置 template <class T, class Alloc> void list<T, Alloc>::reverse() { if (node->next == node || link_type(node->next)->next == node) return; iterator first = begin(); ++first; while (first != end()) { iterator old = first; ++first; transfer(begin(), old, first); } }
直接用STL中的list华丽的超时代码：
#include<stdio.h> #include<iostream> #include<dequ> #include<algorithm> using namespace std; list<int>li; list<int>::iterator it,l,r; int main() { int _case,n; int i,x,lj,rj,step; scanf("%d",&_case); while(_case--) { li.clear(); scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&x); li.push_back(x); } scanf("%d%d",&lj,&rj); l=li.begin(); r=li.begin(); for(i=1;i<lj;i++)l++; for(i=1;i<rj;i++)r++; scanf("%d",&step); for(i=0; i<step; i++) { char s[20]; char c; getchar(); scanf("%s",s); if(s[0]=='I') { getchar(); scanf("%c%d",&c,&x); //puts(c); //printf("%c",c); if(c=='L')// add before,f b { l=li.insert(l,x); } else { r++; r=li.insert(r,x); } } else if(s[0]=='D') { getchar(); scanf("%c",&c); if(c=='R') { r=li.erase(r); if(r==li.end()&&r!=li.begin())r--; } else { l=li.erase(l); //if(l==li.end()&&l!=li.begin())l--; } } else if(s[0]=='R') { if(r!=li.end())r++; reverse(l,r); r--; } else { getchar(); scanf("%c",&c); if(s[4]=='L') { if(c=='L') { if(l!=li.begin())l--; } else { if(r!=li.begin())r--; //printf("%% "); } } else { if(c=='L') { if(l!=li.end())l++; } else { if(r!=li.end())r++; } } } //cout<<*l<<' '<<*r<<endl; } it=li.begin(); printf("%d",*it); it++; for(; it!=li.end(); it++) printf(" %d",*it); printf(" "); } return 0; }
数组模拟双向链表：
自己写的戳：
#include<stdio.h> #define Max 1001000 struct node { int fr;//front int be;//behind int val;//value bool flag; } num[Max];; //int int n,m,l,r,x; void Moveleft(char c) { if(c=='L'&&num[l].fr!=0) l=num[l].fr; else r=num[r].fr; } void Moveright(char c) { if(c=='R'&&num[r].be!=n+1) r=num[r].be; else l=num[l].be; } void InsertL() { num[++n].val=x; num[n].flag=0; num[n].fr=num[l].fr; num[n].be=l; num[num[l].fr].be=n; num[l].fr=n; l=n;//turn left; } void InsertR() { printf("##"); num[++n].val=x; num[n].flag=0; num[n].fr=r; num[n].be=num[r].be; num[num[r].be].fr=n; num[r].be=n; r=n; } void DeleteL() { num[num[l].fr].be=num[l].be; num[num[l].be].fr=num[l].fr; l=num[l].be; } void DeleteR() { num[num[r].fr].be=num[l].be; num[num[r].be].fr=num[l].fr; r=num[r].fr; } void Reverse() { num[r].flag=1; // num[num[l].fr].be=r; num[num[r].be].fr=l;//num[l].fr; int x=num[l].fr; num[l].fr=num[r].be; num[r].be=x; num[num[l].fr].flag=l; //num[num[r].fr].flag=1; //num[r].be=num[r],fr; } void Myprintf() { printf("##%d%d ",l,r); int ret=0; int x=0; x=num[x].be; if(x!=m)printf("%d",num[x].val); ret^=num[x].flag; if(!ret)//equal 0 x=num[x].be; else x=num[x].fr; while(x!=m) { printf(" %d",num[x].val); if(!ret)//equal 0 x=num[x].be; else x=num[x].fr; ret^=num[x].flag; //printf(" $%d$ ",ret); } printf(" "); } int main() { int _case,step; int i; scanf("%d",&_case); while(_case--) { scanf("%d",&n); num[0].be=1; for(i=1; i<=n; i++) { scanf("%d",&num[i].val); num[i].fr=i-1; num[i].be=i+1; num[i].flag=0; } m=++n; scanf("%d %d",&l,&r); scanf("%d",&step); Myprintf(); while(step--) { char op[20],loc[20]; scanf("%s",op); if(op[0]=='R')//reverse Reverse(); else if(op[0]=='I')//insert { scanf("%s %d",loc,&x); if(loc[0]=='R') InsertR(); else InsertL(); } else if(op[0]=='D')//delete { scanf("%s",loc); if(loc[0]=='R') DeleteR(); else DeleteL(); } else//Move { scanf("%s",loc); if(op[4]=='R') Moveright(loc[0]); else Moveleft(loc[0]); } Myprintf(); } Myprintf(); } return 0; }
参考代码（高明之处 运用了四个左右指针，判断相对位置）：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int n1,n2,key; }; node a[1000005]; int L,R,e,n,C,Q,fL,fR; void init() { scanf("%d",&n); int i; for(i=1; i<=n; i++) { scanf("%d",&a[i].key); a[i].n1=i-1; a[i].n2=i+1; } a[0].n2=1; a[n+1].n1=n; e=n+2; scanf("%d%d",&L,&R); fL=a[L].n1; fR=a[R].n2; } void moveLeftL() { if(a[fL].n1==L) L=fL,fL=a[fL].n2; else L=fL,fL=a[fL].n1; } void moveLeftR() { if(a[R].n1==fR) fR=R,R=a[R].n2; else fR=R,R=a[R].n1; } void moveRightL() { if(a[L].n1==fL) fL=L,L=a[L].n2; else fL=L,L=a[L].n1; } void moveRightR() { if(a[fR].n1==R) R=fR,fR=a[fR].n2; else R=fR,fR=a[fR].n1; } void insertL(int x) { a[e].key=x; a[e].n1=fL; a[e].n2=L; if(a[fL].n1==L) a[fL].n1=e; else a[fL].n2=e; if(a[L].n1==fL) a[L].n1=e; else a[L].n2=e; L=e++; } void insertR(int x) { a[e].key=x; a[e].n1=R; a[e].n2=fR; if(a[R].n1==fR) a[R].n1=e; else a[R].n2=e; if(a[fR].n1==R) a[fR].n1=e; else a[fR].n2=e; R=e++; } void deleteL() { int next; if(a[L].n1==fL) next=a[L].n2; else next=a[L].n1; if(a[fL].n1==L) a[fL].n1=next; else a[fL].n2=next; if(a[next].n1==L) a[next].n1=fL; else a[next].n2=fL; L=next; } void deleteR() { int next; if(a[R].n1==fR) next=a[R].n2; else next=a[R].n1; if(a[fR].n1==R) a[fR].n1=next; else a[fR].n2=next; if(a[next].n1==R) a[next].n1=fR; else a[next].n2=fR; R=next; } void reverse() { if(a[fL].n1==L) a[fL].n1=R; else a[fL].n2=R; if(a[L].n1==fL) a[L].n1=fR; else a[L].n2=fR; if(a[R].n1==fR) a[R].n1=fL; else a[R].n2=fL; if(a[fR].n1==R) a[fR].n1=L; else a[fR].n2=L; int k; k=L; L=R; R=k; } void print() { bool tag=false; fL=0; L=a[fL].n2; while(L!=n+1) { if(tag) putchar(' '); else tag=true; printf("%d",a[L].key); if(a[L].n1==fL) fL=L,L=a[L].n2; else fL=L,L=a[L].n1; } puts(""); } int main() { for(scanf("%d",&C); C--;) { init(); scanf("%d",&Q); char op[20],s[20]; int X; while(Q--) { scanf("%s",op); if(!strcmp(op,"MoveLeft")) { scanf("%s",s); if(s[0]=='L') moveLeftL(); else moveLeftR(); } else if(!strcmp(op,"MoveRight")) { scanf("%s",s); if(s[0]=='L') moveRightL(); else moveRightR(); } else if(!strcmp(op,"Insert")) { scanf("%s%d",s,&X); if(s[0]=='L') insertL(X); else insertR(X); } else if(!strcmp(op,"Delete")) { scanf("%s",s); if(s[0]=='L') deleteL(); else deleteR(); } else reverse(); } print(); } return 0; }