1025. 反转链表 (25)
时间限制
300 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue
给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218输出样例：
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
//第一条陷阱是所给结点不一定是链表里的，也就是说可能存在废结点，
//这点题目没说，如果没接触过相关题目，可以说非常隐蔽。
//第二条陷阱是初次接触这种题，可能会忘了仔细看样例：
//反转后，链表结点的值虽然不变，但是其前后结点的地址都要重新调整
//第三条陷阱就是千万别忘了反转后，最后一个结点的地址一定改为-1//用固定分配内存的方式，还是很惨痛，大数据样例没有通过，运行超时
#include <cstdio>
#include <algorithm>
#define MAX 100005
using namespace std;struct node{int address;int data;int next;int num;bool operator < (const struct node &b)const{return num<b.num;}
}node[MAX];int main(){int start,n,k;scanf("%d%d%d",&start,&n,&k);for(int i=0;i<n;i++){scanf("%d%d%d",&node[i].address,&node[i].data,&node[i].next);node[i].num=111111;}int tag=0;//也可以存储 有效链表结点 //这个地方复杂度过高------------------------------------- //直接用address来访问下一个结点 比 这样循环方便得多 while(start!=-1){for(int i=0;i<n;i++){if(start==node[i].address){node[i].num=tag++;start=node[i].next;break;}}}sort(node,node+n);
// printf("tag:%d\n",tag);
// for(int i=0;i<tag;i++){
// printf("%d %05d %d ",node[i].num,node[i].address,node[i].data);
// if(node[i].next!=-1){
// printf("%05d\n",node[i].next);
// }else{
// printf("%d\n",node[i].next);
// }
// }int times=tag/k;int count=1;while(count<=times){int flag=k;for(int i=count*k-1;flag>0;i--){printf("%05d %d ",node[i].address,node[i].data);if(flag>1){printf("%05d\n",node[i-1].address);}else if(flag==1&&count<times){printf("%05d\n",node[(count+1)*k-1].address);}else if(flag==1&&count==times){if(times*k==tag){//反转链表最后一个元素，且是整个链表的最后一个元素 printf("-1\n"); }else{//反转链表最后一个元素 printf("%05d\n",node[times*k].address);}}flag--;} count++;}for(int i=times*k;i<tag;i++){printf("%05d %d ",node[i].address,node[i].data);if(i==tag-1){printf("-1\n");}else{printf("%05d\n",node[i].next);}}return 0;
}上面这段程序大数据样例没通过，原因写在了代码注释里。
下面这段AC代码是在上面这段代码基础上修改的。
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
//依照之前的方法，排出有效结点的时间复杂度略高，考虑大数据无法在限定时间内得出答案
//所以，一个基于之前的设想就是，利用空间复杂度换取时间复杂度
struct node{int addr;int data;int next;
}; int main(){vector<node> vin(100005);//保存存进去的所有结点 ,此时结点的地址即为在这个vector里的地址 vector<node> vsorted;//按地址顺序存储链表结点int first,n,k;cin>>first>>n>>k;struct node temp;for(int i=0;i<n;i++){cin>>temp.addr>>temp.data>>temp.next;vin[temp.addr]=temp;} while(first!=-1){ //关键temp=vin[first];vsorted.push_back(temp);first=temp.next;}int so_size=vsorted.size();
// for(int i=0;i<so_size;i++){
// printf("%05d %d %05d\n",vsorted[i].addr,vsorted[i].data,vsorted[i].next);
// }int times=so_size/k;int count=1;while(count<=times){int flag=k;for(int i=count*k-1;flag>0;i--){printf("%05d %d ",vsorted[i].addr,vsorted[i].data);if(flag>1){printf("%05d\n",vsorted[i-1].addr);}else if(flag==1&&count<times){printf("%05d\n",vsorted[(count+1)*k-1].addr);}else if(flag==1&&count==times){if(times*k==so_size){//反转链表最后一个元素，且是整个链表的最后一个元素 printf("-1\n"); }else{//反转链表最后一个元素 printf("%05d\n",vsorted[times*k].addr);}}flag--;}count++;}for(int i=times*k;i<so_size;i++){printf("%05d %d ",vsorted[i].addr,vsorted[i].data);if(i==so_size-1){printf("-1\n");}else{printf("%05d\n",vsorted[i].next);}}return 0;
} 看网上的菊苣们很多都是用的离散存储的方式。所以。。。