1032 Sharing (25 分)

題意 ：

• suffix后綴；prefix前綴
• 每個結點存一個字母，一共存兩個單詞
• 分別給兩個單詞的第一個字母的地址以及總共的結點數
• 給出所有結點的地址數值和下一個結點的地址（null就是-1）
• 要求這兩個單詞最長公共后綴的起始位置的結點的地址，沒有就輸出-1

思路 ：

• 講了一堆，模擬樣例一發現就是找到兩個鏈表中第一個擁有相同地址的結點，并輸出這個地址，如果沒有這個結點，就輸出-1
• 只要把第一個鏈表中每個地址都標記，遍歷第二個鏈表的時候如果當前這個結點的地址被標記過，就return
• 結點值和結點的下一個結點的地址，可以分別用兩個數組存儲，因為這里的地址最多是5位數，可以充當數組下標；e數組表示地址對應的結點值；ne數組表示地址對應下一個結點的地址
• 鏈表的表頭地址很重要

語法 ：

• 5位地址，輸出記得格式化

#include <iostream> using namespace std;const int N = 1e5 + 10;int n; int h1, h2, ne[N]; char e[N]; bool st[N];int main() {scanf("%d%d%d", &h1, &h2, &n);int address, next;char data;for (int i = 0; i < n; i ++ ){scanf("%d %c %d", &address, &data, &next);e[address] = data, ne[address] = next;}for (int i = h1; ~i; i = ne[i])st[i] = true;for (int i = h2; ~i; i = ne[i])if (st[i]){printf("%05d\n", i);return 0;}puts("-1"); }

1052 Linked List Sorting (25 分)

題意 ：

• 給一個鏈表，要求按照值排序后，輸出鏈表

思路 ：

• 本題可能包含不在鏈表中的結點，這些結點無需統計（從它問你結點數推測），因此另外開一個vector重新建立鏈表
• 鏈表可能為空
• 且有可能同一個結點輸入多次，所以用map存地址對應的結點更好
• 以上這些題目都沒有告訴你。。
• 我們這里的地址用string而不用int，好處是就不需要格式化%05d了，它這樣用到的地址全部是輸入給你的地址，不會由于int和string的轉換失去前導零

語法 ：

• for中可以string做循環變量，通過map重建vector版本鏈表

#include <iostream> #include <unordered_map> #include <vector> #include <algorithm> using namespace std;struct Node {string address;int key;string next;bool operator< (const Node& t) const{return key < t.key;} };int main() {int n;char head[10];scanf("%d %s", &n, head);unordered_map<string, Node> map;char address[10], next[10];int key;while (n -- ){scanf("%s %d %s", address, &key, next);map[address] = {address, key, next};}vector<Node> nodes;for (string i = head; i != "-1"; i = map[i].next) nodes.push_back(map[i]);printf("%d ", (int)nodes.size());if (nodes.empty()) puts("-1");else{sort(nodes.begin(), nodes.end());printf("%s\n", nodes[0].address.c_str());for (int i = 0; i < nodes.size(); i ++ ){if (i + 1 == nodes.size())printf("%s %d -1", nodes[i].address.c_str(), nodes[i].key);elseprintf("%s %d %s\n", nodes[i].address.c_str(), nodes[i].key, nodes[i + 1].address.c_str());}} }

1074 Reversing Linked List (25 分)

題意 ：

• 給一個鏈表和一個k，要求每k個結點為一組逆序，輸出逆序后的鏈表

思路 ：

• 按邏輯順序將鏈表的地址放入vector中
• 注意輸出鏈表的時候不是輸出ne，而是輸出q[i + 1]

#include <iostream> #include <vector> #include <algorithm> using namespace std;const int N = 1e5 + 10;int n, head, m; int e[N], ne[N];int main() {scanf("%d%d%d", &head, &n, &m);int address, data, next;for (int i = 0; i < n; i ++ ){scanf("%d%d%d", &address, &data, &next);e[address] = data, ne[address] = next;}vector<int> q;for (int i = head; ~i; i = ne[i]) q.push_back(i);for (int i = 0; i + m - 1 < q.size(); i += m ){reverse(q.begin() + i, q.begin() + i + m);}for (int i = 0; i < q.size(); i ++ ){printf("%05d %d ", q[i], e[q[i]]);if (i != q.size() - 1) printf("%05d\n", q[i + 1]);else printf("-1\n");} }

1097 Deduplication on a Linked List (25 分)

題意 ：

• data deduplication 重復元素刪除

#include <iostream> #include <cstring> #include <vector>using namespace std;const int N = 100010;int n; int h, e[N], ne[N]; bool st[N];int main() {scanf("%d%d", &h, &n);for (int i = 0; i < n; i ++ ){int address, key, next;scanf("%d%d%d", &address, &key, &next);e[address] = key, ne[address] = next;}vector<int> a, b;for (int i = h; i != -1; i = ne[i]){int v = abs(e[i]);if (st[v]) b.push_back(i);else{st[v] = true;a.push_back(i);}}for (int i = 0; i < a.size(); i ++ ){printf("%05d %d ", a[i], e[a[i]]);if (i + 1 == a.size()) puts("-1");else printf("%05d\n", a[i + 1]);}for (int i = 0; i < b.size(); i ++ ){printf("%05d %d ", b[i], e[b[i]]);if (i + 1 == b.size()) puts("-1");else printf("%05d\n", b[i + 1]);}return 0; }

1133 Splitting A Linked List (25 分)

題意 ：

• Splitting A Linked List 鏈表元素分類
• 給定一個單鏈表，請編寫程序將鏈表元素進行分類排列，使得所有負值元素都排在非負值元素的前面，而 [0,K] 區間內的元素都排在大于 K 的元素前面。
• 但每一類內部元素的順序是不能改變的。

語法 ：

• a.insert(a.end(), b.begin(), b.end());，在vector a容器的末尾加入vector b容器

#include <iostream> #include <cstring> #include <vector>using namespace std;const int N = 100010;int n, k; int h, e[N], ne[N];int main() {scanf("%d%d%d", &h, &n, &k);for (int i = 0; i < n; i ++ ){int address, key, next;scanf("%d%d%d", &address, &key, &next);e[address] = key, ne[address] = next;}vector<int> a, b, c;for (int i = h; i != -1; i = ne[i]){int v = e[i];if (v < 0) a.push_back(i);else if (v <= k) b.push_back(i);else c.push_back(i);}a.insert(a.end(), b.begin(), b.end());a.insert(a.end(), c.begin(), c.end());for (int i = 0; i < a.size(); i ++ ){printf("%05d %d ", a[i], e[a[i]]);if (i + 1 == a.size()) puts("-1");else printf("%05d\n", a[i + 1]);}return 0; }

總結

以上是生活随笔為你收集整理的PAT甲级题目翻译+答案 AcWing（链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。