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.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16Sample 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
错误代码：
1 | #include<iostream> |
上面这段代码可以通过PAT的前五个测试点，最后两个测试点却过不了，参考mooc中这道题的讲解，说明了最后一个测试点是有多余的结点的，比如：1
2
3
4
5
6
700000 6 3
00000 0 00001
00001 1 00002
00002 2 00003
00003 3 00004
00004 4 -1
00005 5 -1
可以看出最后一个结点是多余的，因为到结点00004 4 -1就结束了，最后一个结点没用，所以正确的反转顺序是
1 | 00002 2 00001 |
修改后的代码如下：
（测试点6过了，但是测试点5仍然过不了，运行超时错误）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
struct ListNode
{
string address;
int data;
string next;
};
bool Search(vector<ListNode> &LnVec, string address, string &next, int &position)
{
for(int i = 0; i < LnVec.size(); ++i)
{
if(address == LnVec[i].address)
{
position = i;
next = LnVec[i].next;
return true;
}
}
return false;
}
int main()
{
string beginAddress;
int N = 0, K = 0;
cin >> beginAddress >> N >> K;
vector<ListNode> LnVec;
ListNode LN;
for(int i = 0; i < N; ++i)
{
cin >> LN.address >> LN.data >> LN.next;
LnVec.push_back(LN);
}
stack<ListNode> LnStk;
string tempAddress = beginAddress;
string tempNext;
int reverseNum = N / K; //total reverse times
int countNum = 0; //actual reverse times
int position = 0;
for(int i = 0; i < N; ++i)
{
if(Search(LnVec, tempAddress, tempNext, position))
{
tempAddress = tempNext;
LnStk.push(LnVec[position]);
}
else
{
while(!LnStk.empty() && LnStk.size() != 1 )
{
LnStk.pop();
}
cout << LnStk.top().address <<endl;
tempAddress = LnStk.top().address;
break;
}
if(LnStk.size() == K)
{
++countNum;
if(countNum != 1)
{
cout << LnStk.top().address << endl;
}
for(int j = 0; j < K; ++j)
{
cout << LnStk.top().address << " " << LnStk.top().data << " ";
LnStk.pop();
if(!LnStk.empty())
{
cout << LnStk.top().address << endl;
}
}
if(countNum == reverseNum) //check reverse times
{
cout << tempNext << endl;
break;
}
}
}
while(tempAddress != "-1")
{
Search(LnVec, tempAddress, tempNext, position);
cout << LnVec[position].address << " "
<< LnVec[position].data << " "
<< LnVec[position].next << endl;
tempAddress = tempNext;
}
return 0;
}
超时错误，从代码中知道自己在for循环里加了Search函数，
search函数搜索是遍历整个vector函数来搜索，这样就导致了算法的复杂度是O(n^2);所以需要优化，看网上有人直接以数组存储，直接创建大小为100000的数组，以空间来换时间，这种方法应该可行，但是不太好，我参考这篇文章,使用map，将地址当作key，这样就不用查找，会降低耗时。（map查找速率是O(logn))
下面是AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#include<iostream>
#include<string>
#include<stack>
#include<map>
using namespace std;
struct ListNode
{
string address;
int data;
string next;
};
int main()
{
string beginAddress;
int N = 0, K = 0;
cin >> beginAddress >> N >> K;
map<string,ListNode> LnMap;
ListNode LN;
for(int i = 0; i < N; ++i)
{
cin >> LN.address >> LN.data >> LN.next;
LnMap[LN.address] = LN;
}
stack<ListNode> LnStk;
string tempAddress = beginAddress;
string tempNext;
int reverseNum = N / K; //total reverse times
int countNum = 0; //actual reverse times
for(int i = 0; i < N; ++i)
{
if(tempAddress != "-1")
{
LnStk.push(LnMap[tempAddress]);
tempAddress = LnStk.top().next;
}
else //防止出现多余的结点，主要是应对最后一个测试点
{
while(!LnStk.empty() && LnStk.size() != 1 )
{
LnStk.pop();
}
cout << LnStk.top().address <<endl;
tempAddress = LnStk.top().address;
break;
}
if(LnStk.size() == K) //reverse
{
++countNum;
if(countNum != 1)
{
cout << LnStk.top().address << endl;
}
for(int j = 0; j < K; ++j)
{
cout << LnStk.top().address << " " << LnStk.top().data << " ";
LnStk.pop();
if(!LnStk.empty())
{
cout << LnStk.top().address << endl;
}
}
if(countNum == reverseNum) //check reverse times
{
cout << tempAddress << endl;
break;
}
}
}
while(tempAddress != "-1") //遍历剩下的N%K个结点
{
cout << LnMap[tempAddress].address << " "
<< LnMap[tempAddress].data << " "
<< LnMap[tempAddress].next << endl;
tempAddress = LnMap[tempAddress].next;
}
return 0;
}
我采用的是用栈来存储需要reverse的元素，然后栈的size达到K，pop序列即是reverse后的顺序，但是需要注意的是要考虑到每次reverse后，这一段元素的最后一个Next地址是下一段元素的Address，所以才会有countNum是否为1，栈是否为空的判断，因为每个段reverse序列的最后一个元素，即栈底元素的next是作废的，不应该遍历出来，他的next应该是下一段reverse序列的首元素的地址。这是一种取巧行为，实际上并没有按照出题者的意图通过真正的reverse 链表来操作，黑盒测试，只是输出了结果。
上传截图很麻烦，直接copy结果过来如下：
测试结果：1
2
3
4
5
6
70 答案正确 1 180 12/12
1 答案正确 1 308 3/3
2 答案正确 1 308 2/2
3 答案正确 1 308 2/2
4 答案正确 1 308 2/2
5 答案正确 379 19380 3/3
6 答案正确 1 256 1/1