Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10
5
) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
题意:给我们一组数据,第一组数据分别是头结点,组数,和翻转的值k。为什么要莫名其妙给我们一个头结点???划重点!随后,就是六祖数据,分别是结点地址,结点值,下一个结点的地址。翻转的意识是,头结点开始以k组数据为一组然后将这组数据翻转过来。值得注意的是,题目给我们的结点不是顺序的,需要我们后续把他们连起来,题意大概就是这么个题意了。
思路:先看看输出,简单利落,就是将翻转后的结点输出,当然前面是它自己的地址,后面是下一个结点的地址。我们首先想到的应该是用连链表的结构来做。但是要知道,我们的链表结构体的一个结点,在我们申请后就已经自动给我们分配了一个内存地址,这与题意的模拟地址不符,那我起码得扩充结构体申请三个数据位。但是这样做又是画蛇添足了。所以,只需要申请两个数组模拟链表就好了
1 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<stdio.h> #define max 100008 using namespace std; int main(){ int data[max]; int next[max]; int list[max]; int firstnode , n ,k ; int temnode ,temdata ,temnext; cin>>firstnode>>n>>k; for(int i=0;i<n;i++){ cin>>temnode>>temdata>>temnext; data[temnode]=temdata; next[temnode]=temnext; } //接下来从题给我们的头结点,把结点给理顺,之前说了给的结点不是顺序关系,理顺后我们再对其反转 int sum=0; while(firstnode!=-1){ list[sum++]=firstnode; firstnode=next[firstnode]; } for(int i=0;i<sum-sum%k;i+=k){ for(int j=0;j<k/2;j++){ int t=list[i+j]; list[i+j]=list[i+k-j-1]; list[i+k-j-1]=t; } } //最后我们输出,对于数值和下一结点,我们只需要调用先前存好的数组,调用该数组便可以找到我们需要值和下一结点 for(int i=0;i<sum-1;i++) printf("%05d %d %05d\n",list[i],data[list[i]],list[i+1]); printf("%05d %d -1\n",list[sum-1],data[list[sum-1]]); return 0; } |