题目详情
给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
1
2
3
4
5
6
7
| 00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
|
输出样例：
1
2
3
4
5
6
| 00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
|
作者：CHEN, Yue
单位：浙江大学
代码长度限制：16 KB
时间限制：400 ms
内存限制：64 MB
分析
本题考查对链表的查找与修改以及图、顺序表的使用。
输入的数据为乱序，因此如何按节点地址的顺序快速找到对应的节点并构建成完整的初始链表是本题的一大难点。这里可以利用图（字典），将每个节点的当前地址作为键，映射到作为对应值的节点，指针找到当前节点，将其放入列表中，更新指针指向下一个节点的地址，直至找不到下一个节点为止。
之后k个为一组进行节点的反转，注意边界条件是索引index满足不超过末尾元素索引值index < lst.size()同时保证最后不到k个节点不反转，即lst.size() - index >= k.
注意最后输出前将每个节点的.next修改为下一个节点的.address.
C++
实现
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
| #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
struct node{
string address;
int data;
string next;
bool operator < (node a){
return this->next == a.address;
}
};
int main(){
string first;
int num;
int k;
cin >> first >> num >> k;
vector<node> lst;
map<string, node> dict;
for (int i = 0; i < num; ++i) {
string address;
int data;
string next;
cin >> address >> data >> next;
node tmp {address, data, next};
dict.insert(map<string, node>::value_type(address, tmp));
}
string p = first;
while (dict.count(p) != 0){
lst.push_back(dict[p]);
p = dict[p].next;
}
int index = 0;
vector<node>::iterator it1;
vector<node>::iterator it2;
while (index < lst.size() && lst.size() - index >= k){
it1 = lst.begin();
advance(it1, index);
it2 = it1;
advance(it2, k);
reverse(it1, it2);
index += k;
}
for (int j = 0; j < lst.size(); ++j) {
if(j + 1 <= (lst.size() - lst.size() % k)){
if(j != lst.size() - 1){
lst[j].next = lst[j + 1].address;
} else{
lst[j].next = "-1";
}
}
cout << lst[j].address << " " << lst[j].data << " " << lst[j].next << endl;
}
return 0;
}
|
结果
AC
Python
代码较C++简单，如下
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| basis = input().split()
dic = {}
lst = []
for i in range(0, int(basis[1])):
tmp = input().split()
dic.update({tmp[0]: tmp})
p = basis[0]
while p in dic.keys():
lst.append(dic[p])
p = dic[p][2]
index = 0
while index < len(lst) and len(lst) - index >= int(basis[2]):
for j in range(index, (2 * index + int(basis[2]) - 1) // 2 + 1):
lst[j], lst[int(basis[2]) - j - 1] = lst[int(basis[2]) - j - 1], lst[j]
index += int(basis[2])
for i in range(0, len(lst)):
if i + 1 <= (len(lst) - len(lst) % int(basis[2])):
if i != len(lst) - 1:
lst[i][2] = lst[i + 1][0]
else:
lst[i][2] = "-1"
print(lst[i][0], lst[i][1], lst[i][2])
|
结果
一开始我是用Python写的这题，但是其中有一个输入超时，因此后面改用C++.
