PAT A1074 Reversing Linked List(C++)

发表于 | 分类于 | |
字数统计: 319 字 | 阅读时长 ≈ 2 分钟
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;
}