02-1. Reversing Linked List (25)

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

CHEN, Yue

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⁵) 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 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218

Sample Output:

00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1

 

这题用二维数组高维代表首地址啊address，低维[address][0]储存data,[address][1]则储存next，牺牲空间换时间。

再使用维数组list进行reverse.

1 int list[100010]; 2 int node[100010][2]; 3  4     int st,num,r; 5     cin>>st>>num>>r; 6     int address,data,next,i; 7     for(i=0;i
     
      >address>>data>>next;10         node[address][0]=data;11         node[address][1]=next;12     }
     

先输入node值。如图

address	00000	00100	12309	33218	68237	99999
data	4	1	2	3	6	5
next	99999	12309	33218	00000	-1	68237

 

 

 

值得说明的是：不需要按照顺序输入，到数组中后自然会对应数组的下标值即address。

因此上表中按照数组顺序排序，无初始值的数组下标省略不列。

下面对list赋address.

int m=0,n=st;while(n!=-1){    list[m++]=n;    n=node[n][1];}

list	0	1	2	3	4	5
address	00100	12309	33218	00000	99999	68237

 

 

其中list[0]储存的是st的address，list[1]储存的是st->next的地址，以此类推。直到遇到address为-1.

1 i=0;2 while(i+r<=m)3 {4     reverse(list+i,list+i+r);5     i=i+r;6 }

进行反转，使用algorithm的reverse函数。

1 for (i = 0; i < m-1; i++)2 {3     printf("%05d %d %05d\n", list[i], node[list[i]][0], list[i+1]);4 }5 printf("%05d %d -1\n", list[i], node[list[i]][0]);

最后进行输出，注意的是以int形式储存的，如address中的00000实际储存位置是0，故输出时注意是要用五位数输出。

完整AC代码如下：

1 #include
     
       2 #include
      
        3 using namespace std; 4 int list[100010]; 5 int node[100010][2]; 6 int main() 7 { 8     freopen("F:\\in1.txt","r",stdin); 9     int st,num,r;10     cin>>st>>num>>r;11     int address,data,next,i;12     for(i=0;i
       
        >address>>data>>next;15         node[address][0]=data;16         node[address][1]=next;17     }18     int m=0,n=st;19     while(n!=-1)20     {21         list[m++]=n;22         n=node[n][1];23     }24     i=0;25     while(i+r<=m)26     {27         reverse(list+i,list+i+r);28         i=i+r;29     }30     for (i = 0; i < m-1; i++)31     {32         printf("%05d %d %05d\n", list[i], node[list[i]][0], list[i+1]);33     }34     printf("%05d %d -1\n", list[i], node[list[i]][0]);35 }