PAT乙级1025

https://pintia.cn/problem-sets/994805260223102976/problems/994805296180871168

题解

第一遍没有全部AC,最后1个测试点没过,原因是题目给的结点中有可能有无效结点,所以需要重新统计节点个数。(参考链接:https://blog.csdn.net/m0_37285185/article/details/68936043

修改后全部都AC了。

整体的思路是以地址为键形成一个map,根据从第一个结点开始遍历,统计出有效结点的地址顺序(存储在数组中),最后利用reverse函数将顺序反转,最后将反转的链表输出。

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

// https://pintia.cn/problem-sets/994805260223102976/problems/994805296180871168


#include <map>
#include <algorithm>
using namespace std;

class {
public:
int address;
int data;
int next;

// 因为使用map,所以需要提供一个无参构造
Node(){};

Node(int address,int data,int next){
this->address = address;
this->data = data;
this->next = next;
}
void print(){
printf("%05d", address);
cout << ' ' << data << ' ';
if(next==-1){
printf("%dn",next);
}else{
printf("%05dn", next);
}
}
};

int main()
{
// 获取n、k和首结点地址
int n, k, head;
cin >> head >> n >> k;

// 利用map模拟链表,获取用户输入的结点
int address,data,next;
map<int,Node> nodes;
for(int i=0;i<n;++i){
cin >> address >> data >> next;
nodes[address]=Node(address,data,next);
}


// 获取结点地址的顺序并重新统计结点个数去除无效顶点
int * addressArr=new int[n];
addressArr[0] = head;
address = nodes[head].next;
int nodeCount=1;
while(address!=-1){
addressArr[nodeCount]=address;
nodeCount++;
address = nodes[address].next;
}
n=nodeCount;

// 将结点地址的顺序进行反转
if (k > 1){
int *p = addressArr;
while ((addressArr + n) - p >= k)
{
reverse(p, p + k);
p += k;
}
}

// 更新各结点的next
for(int i=0;i<n-1;++i){
nodes[addressArr[i]].next=addressArr[i+1];
}
nodes[addressArr[n - 1]].next=-1;

// 输出反转后的链表
for (int i = 0; i < n; ++i){
nodes[addressArr[i]].print();
}

// 释放内存
delete[] addressArr;

//system("pause");
return 0;
}

作者:@臭咸鱼

转载请注明出处:https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!