首页 > 代码库 > 02-1 Reversing Linked List （PAT）
02-1 Reversing Linked List （PAT）
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 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 <iostream> 2 #include <string> 3 #include <stdlib.h> 4 #include <iomanip> 5 using namespace std; 6 7 typedef struct{ 8 int data; 9 int next;10 } dataNode;11 12 int ReverseList( dataNode node[], int numNode, int lenSub, int firAdd );13 14 int main()15 {16 //输入处理17 int firAdd, numNode, lenSub;18 //第一行处理19 cin >> firAdd >> numNode >> lenSub;20 dataNode nodes[100000];21 int i;22 int addr, data, next, head;23 for ( i = 0; i < numNode; i++ )24 {25 cin >> addr >> data >> next;26 nodes[ addr ].data =http://www.mamicode.com/ data;27 nodes[ addr ].next = next;28 }29 //排除无效节点，得到有效节点数量30 int noNode = firAdd;31 int realNum = 0;32 while( noNode != -1 )33 {34 noNode = nodes[ noNode ].next;35 realNum++;36 }37 head = ReverseList( nodes, realNum, lenSub, firAdd );38 while ( head != -1 )39 {40 cout << setw(5) << setfill(‘0‘) << head << ‘ ‘;41 cout << nodes[ head ].data << ‘ ‘;42 if ( nodes[ head ].next == -1 )43 {44 cout << nodes[ head ].next << endl;45 }46 else47 {48 cout << setw(5) << setfill(‘0‘) << nodes[ head ].next << endl;49 }50 51 head = nodes[ head ].next;52 }53 //输出处理54 return 0;55 }56 57 int ReverseList( dataNode nodes[], int numNode, int lenSub, int firAdd )58 {59 if ( lenSub > numNode || nodes == NULL || firAdd == -1 ) return firAdd;60 int current = firAdd;61 int prev = -1;62 int next = -1;63 int count = 0;64 while ( current != -1 && count < lenSub )65 {66 next = nodes[ current ].next;67 nodes[ current ].next = prev;68 prev = current;69 current = next;70 count++;71 }72 if ( next != -1 )73 {74 nodes[ firAdd ].next = ReverseList( nodes, numNode - lenSub, lenSub, next );75 }76 return prev;77 }
02-1 Reversing Linked List （PAT）