TUNIVERSE

PAT链表笔记

算法 链表
字数统计: 3k阅读时长: 15 min
2023/09/05

PAT考试链表相关笔记

前置知识

数据定义

1
2
3
4
struct Node {
  int data;
  Node *next;
};

创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node* create(vector<int> &arr) {
  Node *pre, *head, *cur;
  head = new Node;  // 头结点不需要数据域
  head -> next = NULL;
  pre = head;
  for (int i = 0; i < arr.size(); i++) {
    cur = new Node;
    cur -> data = arr[i];
    cur -> next = NULL;
    pre -> next = cur;
    pre = cur;
  }
  return head;
}

查找元素

从第一个结点开始不断判断当前结点的数据域是否等于待查找元素

1
2
3
4
5
6
7
8
9
int search(Node *head, int x) {
  int cnt = 0;
  Node *cur = head -> next; // 有头结点从第一个结点开始
  while (cur) {
    if (cur -> data == x) cnt++;
    cur = cur -> next;
  }
  return cnt;
}

插入元素

将x插入以head为头结点的链表的第pos个位置上，即插入完数据域为x的结点是第pos个结点（头结点后的第一个结点是一号位）

1
2
3
4
5
6
7
8
9
void insert(Node *head, int pos, int x) {
  Node *p = head;
  // 找到插入位置的前一个结点
  for (int i = 0; i < pos - 1; i++) p = p -> next;
  Node *q = new Node;
  q -> data = x;
  q -> next = p -> next;
  p -> next = q;
}

删除元素

删除链表上所有值为x的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void del(Node *head, int x) {
  Node *p = head -> next;
  Node *pre = head;
  while (p) {
    if (p -> data == x) {
      pre -> next = p -> next;
      delete(p);
      p = pre -> next;
    } else {
      pre = p;
      p = p -> next;
    }
  }
}

静态链表

对于五位数的地址，没有必要建立动态链表，使用静态链表会方便很多。

1
2
3
4
struct Node {
  typenam data;
  int next;
} node[size];

[1032] Sharing

题目

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.

linked

You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive $N (<= 105)$, where the two addresses are the addresses of the first nodes of the two words, and $N$ is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by $-1$.

Then $N$ lines follow, each describes a node in the format:

1
Address Data Next

where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.

注意点与解析

  • 求两个链表的⾸个共同结点的地址，如果没有，就输出-1.
  • 测试点5：有可能数据相同但是地址不相同
  • ⽤结构体数组存储， node[i] 表示地址为i的结点， key 表示值，next 为下⼀个结点的地址，flag 表示第⼀条链表有没有该结点.遍历第⼀条链表，将访问过的结点的 flag 都标记为true，当遍历第⼆条结点的时候，如果遇到了true的结点就输出并结束程序，没有遇到就输出-1

代码

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
struct Node {
  char key;
  int next;
  bool flag;
} node[100000];

int main() {
  int s1, s2, n, a, b;
  cin >> s1 >> s2 >> n;
  char data;
  for (int i = 0; i < n; i++) {
    scanf("%d %c %d", &a, &data, &b);
    node[a] = {data, b, false};
  }
  for (int i = s1; i != -1; i = node[i].next)
    node[i].flag = true;
  for (int i = s2; i != -1; i = node[i].next) {
    if (node[i].flag) {
      printf("%05d",  i);
      return 0;
    }
  }
  cout << "-1";
  return 0;
}

[1025] Reversing Linked List

题目

Given a constant $K$ and a singly linked list $L$, you are supposed to reverse the links of every $K$ elements on $L$. For example, 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.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive $N (≤10^5)$ which is the total number of nodes, and a positive $K (≤N)$ which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then $N$ lines follow, each describes a node in the format:

1
Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

注意点与解析

  • 把地址为temp的数的数值存⼊data[temp]中，把temp的下⼀个结点的地址存⼊next[temp]中。
  • 不⼀定所有的输⼊的结点都是有⽤的，加个计数器sum，并用list数组来存真正有用的数据，result存翻转的结果

代码

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
int data[100005], next[100005], list[100005], result[100005];

int main() {
  int first, k, n, sum = 0;
  cin >> first >> n >> k;
  int temp;
  for (int i = 0; i < n; i++) {
    cin >> temp;
    cin >> data[temp] >> next[temp];
  }
  while (first != -1) {
    list[sum++] = first;
    first = next[first];
  }
  for (int i = 0; i < sum; i++)
    result[i] = list[i];

  // 局部翻转
  for (int i = 0; i < (sum - sum % k); i++)
    result[i] = list[i / k * k + k - 1 - i % k];

  for (int i = 0; i < sum - 1; i++)
    printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
  // 最后一个结点
  printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
  return 0;
}

[1052] Linked List Sorting

题目

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive $N (<10^5)$ and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by $−1$.

Then $N$ lines follow, each describes a node in the format:

1
Address Key Next

where Address is the address of the node in memory, Key is an integer in $[−10^5, 10^5]$, and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where $N$ is the total number of nodes in the list and all the nodes must be sorted order.

注意点与解析

  • 定义静态链表。其中结点性质由 bool 型变量 flag 定义，用以表示为结点在链表中是否出现。若当 flag 为 false，则表示无效结点(不在链表上的结点)。
  • 进行初始化。令 flag 均为 false 表示初始状下所有结点都是无效结点
  • 由题目给出的链表首地址遍历整条链表并标记有效结点的 flag 为 true，同时计数有效结点的个数 count。
  • 对结点进行排序。排序函数 cmp 的排序原则是:如果 cmp 的两个参数结点中有无效结点，则按 flag 从大到小排序，以把有效结点排到数组左端(因为有效结点的 flag 为1大于无效结点的 flag);否则，按数据域从小到大排序。
  • 由于有效结点已经按照数据域从小到大排序，因此按要求输出有效结点即可。
  • 注意：
    • 可以直接使用 %05d 的输出格式，以在不足5位时在高位补0。但是要注意-1不能使用 %05d 输出，否则会输出 -0001(而不是-1或者-00001)，因此必须要留意-1的输出。
    • 题目可能会有无效结点，即不在题目给出的首地址开始的链表上。
    • 数据里面还有全部是无效的情况，这时就要根据有效结点的个数特判输出 0 -1。

代码

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
int maxn = 100005;
struct Node {
  int addr, val, next;
  bool flag;
};
vector<Node> node(maxn);

int main() {
  for (int i = 0; i < maxn; i++)
    node[i].flag = false;
  int n, head;
  cin >> n >> head;
  int t1;
  for (int i = 0; i < n; i++) {
    cin >> t1;
    cin >> node[t1].val >> node[t1].next;
    node[t1].addr = t1;
  }
  int count = 0;
  for (int p = head; p != -1; p = node[p].next) {
    node[p].flag = true;
    count++;
  }
  if (!count) {
    cout << "0 -1";
    return 0;
  }
  sort(node.begin(), node.end(), [&](Node a, Node b) {
    if (a.flag == false || b.flag == false) {
      return a.flag > b.flag;
    } else {
      return a.val < b.val;
    }
  });

  printf("%d %05d\n", count, node[0].addr);
  for (int i = 0; i < count; i++) {
    if (i != count - 1)
      printf("%05d %d %05d\n", node[i].addr, node[i].val, node[i+1].addr);
    else
      printf("%05d %d -1", node[i].addr, node[i].val);
  }
  return 0;
}

[1097] Deduplication on a Linked List

题目

Given a singly linked list $L$ with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value $K$, only the first node of which the value or absolute value of its key equals $K$ will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given $L$ being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive $N (≤10^5)$ which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

1
Address Key Next

where Address is the position of the node, Key is an integer of which absolute value is no more than $10^4$, and Next is the position of the next node.

Output Specification:

For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

注意点与解析

  • 定义静态链表。其中结点性质由 int 型变量 order 定义，用以表示结点在链表上的序号。由于最后需要先输出所有未删除的结点，然后输出所有被删除的结点，因此不妨在后面的步骤中令未删除的结点的 order 从0开始编号，被删除的结点的 order 从maxn开始编号
  • 初始化。令 order 的初值均为2maxn，这样无效结点就会被区分开来。
  • 设置变量 countValid (初始化为0)，用来记录未删除的有效结点的个数;设置 countRemoved (初始化为0)，用来记录被删除的有效结点的个数。由题目给出的链表首地址遍历整条链表，如果当前访问结点的权值的绝对值还未出现过(可以开一个全局的 bool 数组 isExist 来记录)，那么就把该结点的 order 设为 countValid，然后令 countValid 加1;如果当前访问结点的权值的绝对值已经出现过,那么就把结点的 order 设为 maxn+countRemoved 然后令 countRemoved 加1。这样未删除的结点的 order 就从0开始编号，而被删除的结点就从maxn开始编号。
  • 对结点进行排序，排序函数 cmp 的排序原则是:直接按照结点的 order 从小到大排序。由于未删除的结点的 order 从0开始编号，被删除的结点从maxn开始编号，而无效结点的 order 为初始的2maxn，因此结点的顺序就是按未删除的结点、已删除的结点、无效结点进行排列。
  • 输出链表。记 count 为 countValid 与 countRemoved 之和，之后将 node[0] ~ node[count-1] 输出。
  • 注意:
    • 最后一个未删除结点和最后一个被删除结点单独处理
    • 题目可能会给出无效结点

代码

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
int maxn = 100005;
struct Node {
  int addr, val, next;
  int order;
};
vector<Node> node(maxn);

int main() {
  for (int i = 0; i < maxn; i++)
    node[i].order = maxn * 2;
  int head, n;
  cin >> head >> n;
  int t1;
  for (int i = 0; i < n; i++) {
    cin >> t1;
    cin >> node[t1].val >> node[t1].next;
    node[t1].addr = t1;
  }
  int count1 = 0, count2 = 0;
  vector<bool> fg(10001, false);
  for (int p = head; p != -1; p = node[p].next) {
    if (fg[abs(node[p].val)] == false) {
      node[p].order = count1++;
      fg[abs(node[p].val)] = true;
    } else {
      node[p].order = maxn + count2++;
    }
  }
  if (!(count1 + count2)) {
    cout << "0 -1";
    return 0;
  }
  sort(node.begin(), node.end(), [&](Node a, Node b) {
    return a.order < b.order;
  });
  for (int i = 0; i < count1 + count2; i++) {
    if (i != count1 - 1 && i != count1 + count2 - 1)
      printf("%05d %d %05d\n", node[i].addr, node[i].val, node[i+1].addr);
    else
      printf("%05d %d -1", node[i].addr, node[i].val);
    if (i == count1 - 1)  cout << endl;
  }
  return 0;
}
CATALOG
  1. 1. 前置知识
    1. 1.1. 创建链表
    2. 1.2. 查找元素
    3. 1.3. 插入元素
    4. 1.4. 删除元素
    5. 1.5. 静态链表
  2. 2. [1032] Sharing
    1. 2.1. 题目
      1. 2.1.1. Input Specification:
      2. 2.1.2. Output Specification:
    2. 2.2. 注意点与解析
    3. 2.3. 代码
  3. 3. [1025] Reversing Linked List
    1. 3.1. 题目
      1. 3.1.1. Input Specification:
      2. 3.1.2. Output Specification:
    2. 3.2. 注意点与解析
    3. 3.3. 代码
  4. 4. [1052] Linked List Sorting
    1. 4.1. 题目
      1. 4.1.1. Input Specification:
      2. 4.1.2. Output Specification:
    2. 4.2. 注意点与解析
    3. 4.3. 代码
  5. 5. [1097] Deduplication on a Linked List
    1. 5.1. 题目
      1. 5.1.1. Input Specification:
      2. 5.1.2. Output Specification:
    2. 5.2. 注意点与解析
    3. 5.3. 代码
Total : 65
2024
2023
2022
2021
2020
动态规划 计算机视觉 三维重建 深度学习 查找 教程 MongoDB 数据库 Neo4j MySQL 机器学习 GNN 随笔 托福 故障诊断 Greenplum操作 Linux磁盘扩容 debug记录 环境问题 多维索引 磁盘故障 迁移学习 列存分区 链表 LeetCode 双指针 剪枝 素数 逻辑题 并查集 树的遍历 哈希 字符串 排序 二叉搜索树 数学模拟 图论 完全二叉树 最短路径 贪心 Set AVL树 图模拟 DFS 快乐模拟 拓扑排序 栈 图的遍历 递推 前端 React Webpack Eslint top
算法 华科课程 学习笔记 英语 年末总结 腾讯AI训练营