首页 > 代码库 > PAT-1074
PAT-1074
首先先贴一下题目：
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 33218Sample Output:
00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1
输入：
第一行：链表的首地址add，结点个数n，每隔k个进行一次反转。
接下来的n行：结点的地址address，数据data，下一个结点的地址next。
输出：
反转之后的结果。
建议测试如下几个情况：
1. k=1或者k=n：
00100 6 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
2. 有其他链表干扰（即有多个-1出现）：
00100 6 2
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 -1
99999 5 68237
12309 2 33218
先说一下我的解题思路吧。
1. 首先要处理输入数据。我是用C++中的容器（vector），容器内存储的类型是新建的类Node。
1 class Node 2 { 3 public : 4 int address; 5 int data; 6 int next; 7 Node* nextNode; 8 Node(int a = 0, int d = 0, int n = 0): 9 address(a), data(d), next(n)10 {11 nextNode = NULL;12 }13 };14 int main()15 {16 int add, n, k;17 cin >> add >> n >> k;18 vector<Node> vec;19 // input the data20 for(int i=0; i<n; i++)21 {22 int inputa, inputb, inputc;23 cin >> inputa >> inputb >> inputc;24 Node node(inputa, inputb, inputc);25 vec.push_back(node);26 }27 // ...28 }
2. 这里首先要进行一个预处理，就是按照address对vector内的数据进行升序排序。这么做是为了能增快程序的运行速度，以便通过测试用例5。
1 // define before main2 bool cmp(const Node &a,const Node &b)3 {4 return a.address < b.address;5 }6 int main(){7 // ...8 sort(vec.begin(), vec.end(), cmp);9 }
3. 然后要处理数据，把vecotr内的数据组成单链表。ncount是链表有效结点的数目，p用来遍历myList，q用来遍历myNewList（即反转后的链表）。处理的过程如下：在vector内不断的寻找address为add（即链表头），找到之后放到MyList，然后让it->next成为新的add。不断重复此过程，直到it->next为-1（即链表尾）为止。上面的预处理在这里就起到作用了，如果没有按照address进行升序排序，这个过程会很慢，通不过测试用例。
用while(1)循环，并且当it走到vector的end再让它回到begin，成一个环状。一定会有it->next为-1走出循环，所以不必担心死循环问题。1 Node* myList = new Node(); 2 int ncount = 0; 3 Node *p = NULL; 4 Node *q = NULL; 5 // deal the data from vector to list 6 vector<Node>::iterator it = vec.begin(); 7 while(1) 8 { 9 // find the first node10 if(it->address == add)11 {12 if(myList->nextNode == NULL)13 {14 p = myList->nextNode = new Node(it->address, it->data, it->next);15 }16 else17 {18 p = p -> nextNode = new Node(it->address, it->data, it->next);19 }20 ncount ++;21 if(it -> next == -1)22 break;23 else24 add = it -> next;25 }26 it++;27 if(it == vec.end())28 it = vec.begin();29 }// for
4. 接下来就是反转了，具体的我已经写到注释里了，如果有看不懂的地方可以再评论区里发表评论。
1 // if the k greater than effective data, then output all 2 if(k>ncount) 3 { 4 p = myList; 5 while(p->nextNode != NULL) 6 { 7 p = p -> nextNode; 8 if(p->next != -1) 9 printf("%.5d %d %.5d\n", p->address, p->data, p->next);10 else11 printf("%.5d %d -1\n", p->address, p->data);12 }13 }// if14 else15 {16 Node *myNewList = new Node();17 // 借助栈来完成反转18 stack<Node*> sta;19 // 需要反转几次20 int times = ncount/k;21 // p始终指向MyList22 p = myList;23 // q始终指向MyNewList24 q = myNewList;25 // 进行times次反转26 for(int j=0; j<times; j++)27 {28 for(int m=0; m<k; m++)29 {30 p = p -> nextNode;31 sta.push(p);32 }33 for(int m=0; m<k; m++)34 {35 Node *qt = sta.top();36 sta.pop();37 if(myNewList->nextNode == NULL)38 {39 q = myNewList->nextNode = new Node(qt->address, qt->data, qt->next);40 }41 else42 {43 q = q -> nextNode = new Node(qt->address, qt->data, qt->next);44 }45 }46 } // for47 // 将剩下的节点依次插入到myNewList后面48 while(p -> nextNode != NULL)49 {50 p = p -> nextNode;51 if(myNewList->nextNode == NULL)52 {53 q = myNewList->nextNode = new Node(p->address, p->data, p->next);54 }55 else56 {57 q = q -> nextNode = new Node(p->address, p->data, p->next);58 }59 } // while60 // 输出61 p = myNewList;62 while(p->nextNode != NULL)63 {64 p = p -> nextNode;65 if (p->nextNode != NULL)66 p->next = p->nextNode -> address;67 else68 p->next = -1;69 if(p->next != -1)70 printf("%.5d %d %.5d\n", p->address, p->data, p->next);71 else72 printf("%.5d %d -1\n", p->address, p->data);73 } // while
5. 完整的代码如下：
1 #include <iostream> 2 #include <vector> 3 #include <cstdlib> 4 #include <iomanip> 5 #include <cstdio> 6 #include <stack> 7 #include <algorithm> 8 using namespace std; 9 10 class Node 11 { 12 public : 13 int address; 14 int data; 15 int next; 16 Node* nextNode; 17 Node(int a = 0, int d = 0, int n = 0): 18 address(a), data(d), next(n) 19 { 20 nextNode = NULL; 21 } 22 }; 23 bool cmp(const Node &a,const Node &b) 24 { 25 return a.address < b.address; 26 } 27 int main() 28 { 29 int add, n, k; 30 cin >> add >> n >> k; 31 vector<Node> vec; 32 // input the data 33 for(int i=0; i<n; i++) 34 { 35 int inputa, inputb, inputc; 36 cin >> inputa >> inputb >> inputc; 37 Node node(inputa, inputb, inputc); 38 vec.push_back(node); 39 } 40 sort(vec.begin(), vec.end(), cmp); 41 Node* myList = new Node(); 42 int ncount = 0; 43 Node *p = NULL; 44 Node *q = NULL; 45 // deal the data from vector to list 46 vector<Node>::iterator it = vec.begin(); 47 while(1) 48 { 49 // find the first node 50 if(it->address == add) 51 { 52 if(myList->nextNode == NULL) 53 { 54 p = myList->nextNode = new Node(it->address, it->data, it->next); 55 } 56 else 57 { 58 p = p -> nextNode = new Node(it->address, it->data, it->next); 59 } 60 ncount ++; 61 if(it -> next == -1) 62 break; 63 else 64 add = it -> next; 65 } 66 it++; 67 if(it == vec.end()) 68 it = vec.begin(); 69 }// for 70 // if the k greater than effective data, then output all 71 if(k>ncount) 72 { 73 p = myList; 74 while(p->nextNode != NULL) 75 { 76 p = p -> nextNode; 77 if(p->next != -1) 78 printf("%.5d %d %.5d\n", p->address, p->data, p->next); 79 else 80 printf("%.5d %d -1\n", p->address, p->data); 81 } 82 }// if 83 else 84 { 85 Node *myNewList = new Node(); 86 // 借助栈来完成反转 87 stack<Node*> sta; 88 // 需要反转几次 89 int times = ncount/k; 90 // p始终指向MyList 91 p = myList; 92 // q始终指向MyNewList 93 q = myNewList; 94 // 进行times次反转 95 for(int j=0; j<times; j++) 96 { 97 for(int m=0; m<k; m++) 98 { 99 p = p -> nextNode;100 sta.push(p);101 }102 for(int m=0; m<k; m++)103 {104 Node *qt = sta.top();105 sta.pop();106 if(myNewList->nextNode == NULL)107 {108 q = myNewList->nextNode = new Node(qt->address, qt->data, qt->next);109 }110 else111 {112 q = q -> nextNode = new Node(qt->address, qt->data, qt->next);113 }114 }115 } // for116 // 将剩下的节点依次插入到myNewList后面117 while(p -> nextNode != NULL)118 {119 p = p -> nextNode;120 if(myNewList->nextNode == NULL)121 {122 q = myNewList->nextNode = new Node(p->address, p->data, p->next);123 }124 else125 {126 q = q -> nextNode = new Node(p->address, p->data, p->next);127 }128 } // while129 // 输出130 p = myNewList;131 while(p->nextNode != NULL)132 {133 p = p -> nextNode;134 if (p->nextNode != NULL)135 p->next = p->nextNode -> address;136 else137 p->next = -1;138 if(p->next != -1)139 printf("%.5d %d %.5d\n", p->address, p->data, p->next);140 else141 printf("%.5d %d -1\n", p->address, p->data);142 } // while143 }// else144 return 0;145 }
困扰我两周的难题终于解决了，试验了20多次将近30次，有图为证：
最后再粘一下AC的成果：
PAT-1074
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。