PAT A1074 Reversing Linked List(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1074 Reversing Linked List
中文版:B1025 反转链表

解题思路

将单链表保存到数组中,用逆转函数对特定范围进行逆转,最后按格式输出

易错点

  • 给定单链表可能包含无用结点
  • 地址固定为五位
  • 最后一个结点的 next 输出 -1

也许陌生的知识点

  • reverse(S.begin() + first, S.begin() + last);
    • 对数组 [first, last) 范围内的元素逆转
    • 需要头文件:algorithm

代码示例:

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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct LNode{
int data, next;
}L[100010];
int main(){
int head, A, N, K;
scanf("%d %d %d", &head, &N, &K);
for(int i = 0; i < N; i++){
scanf("%d", &A);
scanf("%d %d", &L[A].data, &L[A].next);
}
vector<int> S;
while(head != -1){ // 遍历单链表,将对应结点地址存放到新数组中
S.push_back(head);
head = L[head].next;
}
for(int i = 0; i + K <= S.size(); i+=K){ // 逆转数组,这里不用N,因为可能包含无用结点
reverse(S.begin() + i, S.begin() + i + K);
}
for(int i = 0; i + 1< S.size(); i++){
printf("%05d %d %05d\n", S[i], L[S[i]].data, S[i+1]);
}
printf("%05d %d -1\n", S.back(), L[S.back()].data);
return 0;
}