02-线性结构3 Reversing Linked List   (25分)

• 时间限制：400ms
• 内存限制：64MB
• 代码长度限制：16kB
• 判题程序：系统默认
• 作者：陈越
• 单位：浙江大学

Given a constant KKK and a singly linked list LLL, you are supposed to reverse the links of every KKK elements on LLL. For example, given LLL being 1→2→3→4→5→6, if K=3K = 3K=3, then you must output 3→2→1→6→5→4; if K=4K = 4K=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 NNN (≤105\le 10^5≤10​5​​) which is the total number of nodes, and a positive KKK (≤N\le N≤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 NNN 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

1 #include
       
         2 using namespace std; 3  4 struct Node 5 { 6     int data; 7     int adr,next; 8 }t; 9 int N,head,K;10 map
        
          Input;//用map储存输入序列，地址作为键值，方便通过地址（head，next）找到相关点11 stack
         
           Sta,T;12 vector
          
            Result(N);//储存结果链表13 vector
           
            ::iterator it;14 int main()15 {16     /*输入*/17     scanf("%d %d %d",&head,&N,&K);18     for(int i=0;i
            
             second;//找到第一个点26 while(num++
             
              second;32 if(num%K==0)//满K个元素，逆序出栈放入Result33 {34 while(!Sta.empty())35 {36 Result.push_back(Sta.top());37 Sta.pop();38 }39 if(flag==-1)//最后一个结点刚好组成最后K个，结束40 break;41 continue;42 }43 else if(flag==-1)//最后一个结点多余，将栈中的点出，入，出栈后恢复正序放入Result，结束44 {45 while(!Sta.empty())46 {47 T.push(Sta.top());48 Sta.pop();49 }50 while(!T.empty())51 {52 Result.push_back(T.top());53 T.pop();54 }55 break;56 }57 }58 /*输出*/59 it=Result.begin();60 printf("%05d %d ",it->adr,it->data);61 it++;62 for(;it!=Result.end();it++)63 {64 printf("%05d\n%05d %d ",it->adr,it->adr,it->data);65 }66 printf("-1\n");67 Input.clear();68 Result.clear();69 return 0;70 }