链表---移动盒子（双向链表）
题目：移动盒子UVa 12657
你有一行盒子，从左到右依次编号为1,2,3,…,n。可以执行以下4种指令：
1 x y：表示把盒子x移动到盒子y的左边（如果x已经在y的左边则忽略此指令）。
2 x y：表示把盒子x移动到盒子y的右边（如果x已经在y的右边则忽略此指令）。
3 x y：表示交换盒子x和y的位置。
4：表示反转整条链。
指令保证合法，即x不等于y。
【输入格式】
输入包含不超过10组数据，每组数据第一行为盒子数n和指令m，以下m行每行包含一条指令。
【输出格式】
每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。
【输入样例】
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
【输出样例】
case 1: 12
case 2: 9
case 3: 2500050000
[作者：大1234草]
原文：(https://blog.csdn.net/sinat_38816924/article/details/83514484)
如果是使用数组会超时。
--->Left[i]和Right[i]分别表示编号为i的盒子左边和右边的盒子编号
但是注意了 如果执行了操作4后， 如果操作1 2操作不变的话， 那么操作1就是2，2 就是1（放在左边 + 反转 = 放在右边）
表格（以样例1为例）
输入6个盒子，4条指令
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Left [i] | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| Right [i] | 6 | 2 | 3 | 4 | 5 | 6 | 0 |
| 盒变化 | |||||||
| 盒子0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 1 4 | |||||||
| 盒子1 | 2 | 3 | 1 | 4 | 5 | 6 | |
| 2 3 5 | |||||||
| 盒子2 | 2 | 1 | 4 | 5 | 3 | 6 | |
| 3 1 6 | |||||||
| 盒子3 | 2 | 6 | 4 | 5 | 3 | 1 | |
| 4 | |||||||
| 盒子4 | 1 | 3 | 5 | 4 | 6 | 2 |
书上代码：
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#define N 100001
using namespace std;
int Left[N],Right[N];//左右盒子编号
int n;
int swap(int a,int b){//交换两个值
int t;
t=a;
a=b;
b=t;
return a,b;
}
//双向链表的一个比较实用的函数
void link(int l,int r){//连接两个节点
Right[l]=r;
Left[r]=l;
}
int main()
{
int m,kase=0;
//n,m分别为盒子个数和指令条数
while(scanf("%d%d",&n,&m)==2){//读取两个整形值到n和m
for(int i=1;i<=n;i++){
Left[i]=i-1;
Right[i]=(i+1)%(n+1);
}
Right[0]=1;
Left[0]=n;
int op,X,Y,inv=0;//inv表示操作4是否执行
while(m--){
scanf("%d",&op);
if(op==4)inv=!inv;//翻转整条链
else {
scanf("%d%d",&X,&Y);
if(op==3&&Right[Y]==X)swap(X,Y);// !为了转换成同一种情况来处理
if(op!=3&&inv)op=3-op;
if(op==1&& X==Left[Y]) continue;
if(op==2&& X==Right[Y])continue;
int LX=Left[X], RX=Right[X],
LY=Left[Y],RY=Right[Y];
//分类讨论
if(op==1){
link(LX,RX);link(LY,X);link(X,Y);
}
else if(op==2){
link(LX,RX);link(Y,X);link(X,RY);
}//X的左右连起来，按照链的顺序来写可能更加清晰
else if(op==3){
if(Right[X]==Y){
link(LX,Y);link(Y,X);link(X,RY);}
else{
link(LX,Y);link(Y,RX);link(LY,X);link(X,RY); }
}
}
}
//奇数位置盒子编号之和
int b=0;
long long ans=0;
for(int i=1;i<=n;i++){
b=Right[b];//向右推移
if(i%2==1)ans+=b;
}
if(inv && n%2==0) ans=(long long)n*(n+1)/2-ans;//
printf("case %d: %lld\n",++kase,ans); //输出
}
return 0;
}
大佬的代码：
链表解法:::作者：不羡
#include<iostream>
using namespace std;
int bigflag = 0;
struct node {
int x;
node * next;
};
int main() {
int n, m;
while (cin >> n >> m)
{
node *head = new node;;
head->x = 1;
node *temp = head;
for (int i = 2; i <= n; i++) {
node *p = new node;
p->x = i;
temp->next = p;
temp = p;
}
temp->next = NULL;
int a, b, c;
for (int flag = 0; flag < m; flag++) {
cin >> a;
if (a == 1) {
cin >> b >> c;
int i, j;
node *zz = head;
node *hh = head;
if (zz->x == b)i = 0;
else {
for (i = 1; i < n; i++) {
if (zz->next->x == b)break;
zz == zz->next;
}
}//真实位置i+1,要单独考虑在头的情况；
if (hh->x == c)j = 0;
else {
for (j = 1; j < n; j++) {
if (hh->next->x == c)break;
hh = hh->next;
}
}//真实情况j+1;
if (i + 1 + 1 != j + 1) {
if (i == 0) {
head = zz->next;
zz->next = hh->next;
hh->next = zz;
}
else {
node *s = new node;
s = zz->next;
zz->next = zz->next->next;
s->next = hh->next;
hh->next = s;
}
}
node * w = head;
}
else if (a == 2) {
cin >> b >> c;
int i, j;
node *zz = head;
node *hh = head;
if (zz->x == b)i = 0;
else {
for (i = 1; i < n; i++) {
if (zz->next->x == b)break;
zz == zz->next;
}
}//真实位置i+1,要单独考虑在头的情况；
for (j = 1; j < n; j++) {
if (hh->x == c)break;
hh = hh->next;
}
if (i + 1 != j + 1) {
if (i == 0) {
head = zz->next;
zz->next = hh->next;
hh->next = zz;
}
else {
node *p = new node;
p = zz->next;
zz->next = zz->next->next;
p->next = hh->next;
hh->next = p;
}
}
}
else if (a == 3) {
cin >> b >> c;
node *zz = head;
node *hh = head;
int i, j;
for (i = 1; i < n; i++) {
if (zz->x == b)break;
zz = zz->next;
}
for (j = 1; j < n; j++) {
if (hh->x == c)break;
hh = hh->next;
}
int temp;
temp = zz->x;
zz->x = hh->x;
hh->x = temp;
node * e = head;
int sum = 0;
}
else if (a == 4) {
node *mid = head;
node *tail = head->next;
for (int i = 1; i < n; i++) {
node *pre = tail->next;
tail->next = mid;
mid = tail;
tail = pre;
}
node *mm = mid;
head = mid;
}
}
node *mark = head;
int sum = 0;
for (int i = 1; i <= n; i = i + 2) {
sum = sum + mark->x;
mark = mark->next->next;
}
cout << "Case "<<bigflag+1<<": "<<sum << endl;
bigflag++;
}
system("pause");
return 0;
