0%

PTA1074 反转链表

题目大意

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.

解题关键

用哈希表存储链表,在链表头需要另外插入一个空节点指向原链表头。
反转的迭代中需要三个临时指针,分别指向被反转节点及其之前、之后的位置。注意逆转节点段头尾的处理。注意链表尾边界情况的处理。

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
#include<iostream>
#include<list>
#include<algorithm>
#include<vector>
class Node {
public:
int key=-1;
int val;
int next;
};
using namespace std;
vector<Node> ahash(100001);
int main() {
int root, n, k;
cin >> root >> n >> k;
int temp1, temp2, temp3;
for (int i = 0; i < n; i++) {
cin >> temp1 >> temp2 >> temp3;
ahash[temp1] = Node({ temp1,temp2,temp3 });
}
ahash[100000].next = root;
int it, preit, postit; //分别指向节点段的末尾,节点段之前,节点段之后
it = root;
preit = 100000;
int count = 1;
while (it != -1) {
if (count != k) {
count++;
it = ahash[it].next;
}
else {
postit = ahash[it].next;
int tempit= ahash[preit].next;
int tempit_ = ahash[tempit].next;
int tempit__ = ahash[tempit_].next;
while(tempit != it) {
ahash[tempit_].next = tempit;
tempit = tempit_;
tempit_ = tempit__;
//注意处理边界情况
if (tempit__ != -1)
tempit__ = ahash[tempit__].next;
}
int newpre = ahash[preit].next;
ahash[newpre].next = postit;
ahash[preit].next = it;

preit = newpre;
it = postit;
count = 1;
}
}
for (int i = ahash[100000].next; i != -1; i = ahash[i].next) {
if(ahash[i].next == -1) printf("%05d %d -1\n", ahash[i].key, ahash[i].val);
else printf("%05d %d %05d\n", ahash[i].key, ahash[i].val, ahash[i].next);
}
return 0;
}