1025 反转链表 (25 分)
起初,在看到这个题目的时候,我理解成将前链表前k个逆置,而且7个点过了5个。所以我也没往理解错题意方面去想。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int first;
int mid;//第k个元素位置
int total,k;
struct Node{
int data;
int pre=-1;//上一节点下标
int next=-1;//下一节点下标
}node[100000];
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int main(){
int adress,data,next;
cin>>first>>total>>k;
for(int i=0;i<total;i++){//输入数据
cin>>adress>>data>>next;
node[adress].data=data;
if(next>=0){
node[next].pre=adress;
}
node[adress].next=next;
}
int i=first;
for(int j=1;j<k;j++){
i=node[i].next;
}
mid=i;
if(total>=k&&k>1){//需要交换
int j=mid;
i=first;
for(int t=1;t<k;t++){
swap(node[j].pre,node[j].next);
j=node[j].next;
}
swap(node[mid].pre,node[i].next);
first=mid;
}
// cout<<node[first].next<<endl;
i=first;
while(i!=-1){
if(node[i].next!=-1){
printf("%.5d %d %.5d\n",i,node[i].data,node[i].next);
}else{
printf("%.5d %d %d\n",i,node[i].data,node[i].next);
}
i=node[i].next;
}
return 0;
}
最后,一直没过,网上在一篇大佬的文章中看到了,才知道自己理解错了题意:真正题意是(每k个节点进行反转):代码如下:
#include<bits/stdc++.h>
using namespace std;
int first,total,k;
vector<pair<int,int>> res;
struct Node{
int data,pre=-1, next=-1;//数据,上一节点下标,下一节点下标
}node[100000];
int main(){
int adress,data,next;
cin>>first>>total>>k;
for(int i=0;i<total;i++){//输入数据
cin>>adress>>data>>next;
node[adress].data=data;
if(next>=0){
node[next].pre=adress;
}
node[adress].next=next;
}
int i=first,j,temp=first;
if(k>=1&&k<=total)
for(int t=0;t<total/k;t++){//总共需要进行total/k次交换
for(int e=1;e<k;e++) i=node[i].next;
temp=i;
for(int e=0;e<k;e++){
res.push_back({temp,node[temp].data});
temp=node[temp].pre;
}
i=node[i].next;
}
while(i!=-1){
res.push_back({i,node[i].data});
i=node[i].next;
}
for(j=0;j<res.size()-1;j++){
printf("%.5d %d %.5d\n",res[j].first,res[j].second,res[j+1].first);
}
printf("%.5d %d %d\n",res[j].first,res[j].second,-1);
return 0;
}
然而,测试点6一直过不了,最后,在一个大佬的博客(https://blog.csdn.net/shiawaseli/article/details/89931327)中找到了原因:链表中可能存在不在链表中的节点(单独存在,是游离节点,与第一个节点地址所在链表没有关系),最后AC代码如下:
#include<bits/stdc++.h>
using namespace std;
int first,total,k;
vector<pair<int,int>> res;
struct Node{
int data,pre=-1, next=-1;//数据,上一节点下标,下一节点下标
}node[100000];
int main(){
int adress,data,next;
cin>>first>>total>>k;
for(int i=0;i<total;i++){//输入数据
cin>>adress>>data>>next;
node[adress].data=data;
if(next>=0){
node[next].pre=adress;
}
node[adress].next=next;
}
int i=first,j,temp=first;
int cnt=1;
while(node[temp].next!=-1){
cnt++;
temp=node[temp].next;
}
if(k>=1&&k<=cnt)
for(int t=0;t<cnt/k;t++){//总共需要进行total/k次交换
for(int e=1;e<k;e++) i=node[i].next;
temp=i;
for(int e=0;e<k;e++){
res.push_back({temp,node[temp].data});
temp=node[temp].pre;
}
i=node[i].next;
}
while(i!=-1){
res.push_back({i,node[i].data});
i=node[i].next;
}
for(j=0;j<res.size()-1;j++){
printf("%.5d %d %.5d\n",res[j].first,res[j].second,res[j+1].first);
}
printf("%.5d %d %d\n",res[j].first,res[j].second,-1);
return 0;
}