PAT A1133 Splitting A Linked List(C++)

发表于 | 分类于 | |
字数统计: 546 字 | 阅读时长 ≈ 3 分钟
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1133 Splitting A Linked List
中文版：B1075 链表元素分类

解题思路

将链表存放到数组中，遍历链表，将对应范围的值加入不同的可变数组中，最后合并数组，顺序输出。

易错点

  • 最后一个结点的 next 地址应当输出 -1
  • 地址的格式为五位数

也许陌生的知识点

  • vector<int> ans;
    • 实现变长数组，元素类型可任意指定
      • ans.push_back(num[i])往变长数组末尾中添加一个元素
      • ans.pop_back()删除变长数组中最后一个元素
    • 需要的头文件：vector

代码示例：

  • 方法一：利用数组存放链表
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
#include <cstdio>
#include <vector>
using namespace std;
int main() {
  int A[100010], D[100010], n, k, pos, now, next, temp;
  vector<int> first, second, last;
  scanf("%d %d %d", &pos, &n, &k);
  for(int i = 0; i < n; i++){
    scanf("%d %d %d",&now, &temp, &next);
    A[now] = next;
    D[now] = temp;
  }
  while(pos != -1){ // 遍历链表
    if(D[pos] < 0) first.push_back(pos);
    else if(D[pos] > k) last.push_back(pos);
    else second.push_back(pos);
    pos = A[pos];
  }
  for(int i = 0; i < second.size(); i++) first.push_back(second[i]);
  for(int i = 0; i < last.size(); i++) first.push_back(last[i]);
  for(int i = 0; i < first.size(); i++){
    if(i == first.size() - 1) printf("%05d %d -1", first[i], D[first[i]]);
    else printf("%05d %d %05d\n", first[i], D[first[i]], first[i + 1]);
  }
  return 0;
}
  • 方法二：利用结构体数组存储链表
    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
    #include <vector>
    #include <cstdio>
    using namespace std;
    struct Node{
      int address, data, next;
    }LNode[100010];
    int main(){
      vector<int> first, second, last;
      int now, n, k, t;
      scanf("%d %d %d", &now, &n, &k);
      for(int i = 0; i < n; i++){
        scanf("%d", &t);
        LNode[t].address = t;
        scanf("%d %d", &LNode[t].data, &LNode[t].next);
      }
      while(now != -1){
        if(LNode[now].data < 0)first.push_back(now);
        else if(LNode[now].data > k) last.push_back(now);
        else second.push_back(now);
        now = LNode[now].next;
      }
      for(int i = 0; i < second.size(); i++) first.push_back(second[i]);
      for(int i = 0; i < last.size(); i++) first.push_back(last[i]);
      for(int i = 0; i < first.size(); i++){
        if(i == first.size() - 1) printf("%05d %d -1", first[i], LNode[first[i]].address);
        else printf("%05d %d %05d\n", first[i], LNode[first[i]].address, first[i + 1]);
      }
      return 0;
    }