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
题目大意：给出n个节点，以及头结点，要求把相邻的k个节点翻转， 如果n不能被k整除，剩下的节点按照原来的顺序
思路：先用vector<int> value保存当前节点的值， vector<int> v保存当前节点指向下一个节点的指针； 然后再根据链表信息把k个链表的信息保存在vector<node> temp中， 然后在反向添加到vector<node> link中；
修改link中链表信息，输出结果
注意点：在使用vector的时候，如果事先申明了vector的大小，如果再使用push_back()在压在申请内存的后面的，而不是从头开始压入的；
此外，pat的链表类题中，经常存在不在链表中的节点， 所以在最后的循环输出的时候，不能以节点个数作为循环结束的判断，应该以link的大小作为循环次数的判断
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 struct Node{ 5 int addr, val, next; 6 }; 7 int main(){ 8 int root, n, k, i, j; 9 scanf("%d %d %d", &root, &n, &k); 10 vector<Node> linkList(100000); 11 for(i=0; i<n; i++){ 12 int addr, val, next; 13 scanf("%d %d %d", &addr, &val, &next); 14 linkList[addr].addr=addr; linkList[addr].val = val; linkList[addr].next = next; 15 } 16 int cnt=(n+k-1)/k, nodeCnt=0; 17 vector<vector<int> > idx(cnt); 18 while(root!=-1){//找出链表中所有节点的位置 19 if(idx[nodeCnt].size()>=k) nodeCnt++; 20 idx[nodeCnt].push_back(root); 21 root = linkList[root].next; 22 } 23 for(i=0; i<cnt-1; i++){//先输出前面完整的分组 24 int len=idx[i].size(); 25 for(j=len-1; j>0; j--){ 26 int index=idx[i][j], preIndex=idx[i][j-1]; 27 if(j!=0) printf("%05d %d %05d ", index, linkList[index].val, preIndex); 28 } 29 if(idx[i+1].size()==k) printf("%05d %d %05d ", idx[i][0], linkList[idx[i][0]].val, idx[i+1][k-1]); 30 else printf("%05d %d %05d ", idx[i][0], linkList[idx[i][0]].val, idx[i+1][0]); 31 } 32 if(idx[cnt-1].size()==k){//处理最后一个分组 33 for(j=k-1; j>0; j--) printf("%05d %d %05d ", idx[cnt-1][j], linkList[idx[cnt-1][j]].val, idx[cnt-1][j-1]); 34 printf("%05d %d %d ", idx[cnt-1][0], linkList[idx[cnt-1][0]].val, -1); 35 }else{ 36 for(i=0; i<idx[cnt-1].size()-1; i++) 37 printf("%05d %d %05d ", idx[cnt-1][i], linkList[idx[cnt-1][i]].val, idx[cnt-1][i+1]); 38 printf("%05d %d %d ", idx[cnt-1][i], linkList[idx[cnt-1][i]].val, -1); 39 } 40 return 0; 41 }