链表翻转
作者:
兜里没有钢镚
,
2022-05-18 22:52:23
,
所有人可见
,
阅读 274
#include<bits/stdc++.h>
using namespace std;
struct Node {
int value;
Node *next,*pre;
}a[100010],*head,*tail;
int n,m;
int main()
{
//1 数据读入
cin>>n>>m;
head = tail = NULL;
for(int i=1;i<=n;i++) {
a[i].value = i;
if(head == NULL) {
head = tail = &a[i];
}
else {
tail ->next = &a[i];
a[i].pre = tail;
tail = &a[i];//更新尾指针
}
}
while(m--) {
//2 寻找pl,pr
int l,r ;
cin>>l>>r;
if(l==r)continue;//一个节点无需交换
Node *pl,*pr;
pl = pr = head;
for(int i=1;i<l;i++) //移动l-1(r-1)即可
pl = pl ->next;
for(int i=1;i<r;i++)
pr = pr ->next;
//3 记录pl的左边 pr的右边
Node *v = pl->pre,*u = pr->next;
//4 进行翻转操作 [l,r]之间
Node *x,*y,*z;
x = pl ; y = x->next;
while(x!=pr) { //x == pr的时候即已经翻转结束
z = y->next;
y -> next = x;
x -> pre = y;
x = y;
y = z;
}
//5 翻转结束之后连接头和尾
if(head == pl){ //头指针等于左端点的情况
head = pr;
pr ->pre = NULL;
}
else {
Node *p = v;
pr -> pre = p;
p -> next = pr;
}
if(tail == pr){ //尾指针等于右端点的情况
tail = pl;
pl -> next = NULL;
}
else {
Node *p = u;
p -> pre = pl;
pl -> next = p;
}
}
//6 数据输出
for(Node *p = head ;p;p=p->next) cout<<p->value<<" ";
return 0;
}
####无注释版本
#include<bits/stdc++.h>
using namespace std;
struct Node{
int value;
Node *next,*prev;
}a[100010],*head,*tail;
int main()
{
int n,m;
cin>>n>>m;
head = tail = NULL;
for(int i=1;i<=n;i++) {
a[i].value = i;
if(head == NULL) {
head = tail = &a[i];
}
else {
tail -> next = &a[i];
a[i].prev = tail;
tail = &a[i];
}
}
while(m--) {
int l,r;cin>>l>>r;
if(l==r) continue;
Node *pl,*pr;
pl = pr = head;
for(int i=1;i<l;i++)pl = pl -> next;
for(int i=1;i<r;i++)pr = pr -> next;
Node *v = pl -> prev;
Node *u = pr -> next;
Node *x,*y,*z;
x = pl ; y = x->next;
while(x != pr){
z = y -> next;
y -> next = x;
x -> prev = y;
x = y;
y = z;
}
if(head == pl){
head = pr;
pr -> prev = NULL;
}
else {
Node *p = v;
p -> next = pr;
pr -> prev = p;
}
if(tail == pr){
tail = pl;
pl -> next = NULL;
}
else {
Node *p = u;
p -> prev = pl;
pl -> next = p;
}
}
for(Node *p = head ; p ; p = p->next) cout<<p->value<<" ";
return 0;
}