题目:
给定一个常数 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
思路:
测试点5 :注意N的大小,以此来设置数组的大小,小了的话数组会溢出(段错误);
测试点6: 注意输入的点有一些可能会是游离的(不在链表内),因此在代码中要把输入的点的个数n改为实际链表中点的个数。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<string.h> using namespace std; struct Node{ string address; int data; string next; Node(){}; Node(string address, int data, string next):address(address),data(data),next(next){}; }node[100005],node1[100005]; int main(){ int n,k,index=0; string a0,a; map<string,int>d; cin>>a0>>n>>k; for(int i=0;i<n;i++){ string address,next; int data; cin>>address>>data>>next; node[i] = Node(address,data,next); d[address] = i; } a = a0; while(a != "-1"){ node1[index++] = node[d[a]]; a = node[d[a]].next; } n = index; for(int i=0;i<n/k;i++){ for(int j=k-1; j>=0; j--){ if(i > 0 && j == k-1){ cout<<node1[i*k+j].address<<endl; } cout<<node1[i*k+j].address<<" "<<node1[i*k+j].data<<" "; if(i*k+j-1 >= 0 && j != 0){ cout<<node1[i*k+j-1].address<<endl; } } } if(n%k == 0){ cout<<"-1"<<endl; }else{ cout<<node1[n-n%k].address<<endl; for(int i=n%k;i>0;i--){ cout<<node1[n-i].address<<" "<<node1[n-i].data<<" "; if(i > 1){ cout<<node1[n-i+1].address<<endl; } } cout<<"-1"<<endl; } return 0; }
标签:1025,结点,int,反转,next,链表,address,data From: https://www.cnblogs.com/yccy/p/16824818.html