PAT甲级1074. Reversing Linked List (25)

    xiaoxiao2021-03-26  8

    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 (<= 105) 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

    #include <cstdio> using namespace std; #include <vector> const int MAX=100000+10; int node[MAX],Next[MAX],previous[MAX]; int main(){ int head,N,K; scanf("%d %d %d",&head,&N,&K); int Address,Data,Next_Address; for(int i=0;i<N;i++){ scanf("%d %d %d",&Address,&Data,&Next_Address); if(Address!=-1){ node[Address]=Data; Next[Address]=Next_Address; } if(Address==head) previous[Address]=-1; if(Next_Address!=-1) previous[Next_Address]=Address; } vector<int> index; int cnt=0;//链表中结点的个数 for(int i=head;i!=-1;i=Next[i]){ index.push_back(i); // printf("previous=%d\n",previous[i]); cnt++; } int round=cnt/K; int m=K-1; int last=-1; while(m<cnt){ int i=m; for(i;i>m-K+1;i--){ printf("d %d d\n",index[i],node[index[i]],previous[index[i]]); } if(m==cnt-1) printf("d %d %d\n",index[i],node[index[i]],-1); else if(m+K>=cnt) printf("d %d d\n",index[i],node[index[i]],index[m+1]); else printf("d %d d\n",index[i],node[index[i]],index[m+K]); m+=K; } for(int i=m-K+1;i<cnt;i++){ if(i!=cnt-1) printf("d %d d\n",index[i],node[index[i]],Next[index[i]]); else printf("d %d %d\n",index[i],node[index[i]],-1); } return 0; }