L2-002 链表去重-团体程序设计天梯赛GPLT

题目来源：团体程序设计天梯赛-练习集
题目地址：L2-002 链表去重

题目大意

将链表数据域的值相同（包含绝对值相同）的节点去掉，然后将去掉的节点又重新组成一条链表，最后输出去重后的链表和被去掉的节点组成的链表。样例表示如下：

题目分析

这道题的题目难度相对较低，只要你熟悉链表的遍历和删除操作，就可以顺利完成这道题。虽然话是那么说，但是用对了数据结构可以让解题事半功倍。

• 设 $lb$ 数组用于存储输入的链表，我们可以用数组下标表示当前节点地址，就可以避免遍历时寻址的麻烦
• 设 $re$ 数组用于存储被去除节点组成的链表，这时我们可以直接顺序存储被去除的节点，而且只需要存储节点的地址和数据域，这样我们就可以利用顺序知道每个下个节点的地址了。
• 事实上，我们可以发现 $lb$ 相当于链表，而 $re$ 相当于顺序表。它们的存储示意图如下：
  

了解到上面这些，写代码已经顺利了（默认你会链表的遍历和删除），最后再说一下写题目踩到的坑：

• 地址直接用 $int$ 类型存储，没必要用 $string$，否则无法用上上述存储结构（别跟我说用 $map$ ，我第一发就是这样超时的）。
• 格式控制符 “%05d” 表示如果输出的字符少于5位时，在左边补 $0$ （默认是补空格）。
• 删除操作需要用到前驱节点 $pre$ 的指针 ，$pre$ 在每次遇到不需要删除的节点时就要更新，如果单纯的直接用上一个节点，就可能用到被去除节点的地址。

代码如下

#include <bits/stdc++.h>using namespace std; const int maxn = 1e5 + 10; int n, cnt; int one, s, pre; /*** lb用于存储原始链表* re用于存储原始链表中的重复节点*/ pair<int, int> lb[maxn]; pair<int, int> re[maxn]; set<int> vis;int main() {cin >> one >> n;for (int i = 1; i <= n; i++) {int address, num, next;cin >> address >> num >> next;lb[address] = make_pair(num, next);}cnt = 0;//遍历链表，s表示当前节点的地址for (s = one; s != -1; s = lb[s].second) {int num = lb[s].first;if (!vis.count(abs(num))) {vis.insert(abs(num));//pre记录下一个节点的前驱节点地址pre = s;} else {//链表删除重复节点操作lb[pre].second = lb[s].second;//将删除的节点存到另一条链表re[cnt].first = num;re[cnt].second = s;cnt++;}}for (s = one; s != -1; s = lb[s].second) {printf("%05d %d ", s, lb[s].first);if (lb[s].second != -1) printf("%05d\n", lb[s].second);else printf("-1\n");}for (int i = 0; i < cnt; i++) {printf("%05d %d ", re[i].second ,re[i].first);if (i != cnt - 1) printf("%05d\n", re[i + 1].second);else printf("-1\n");}return 0; }

---

如果本文对你有所帮助，别忘了点赞哦~

总结

以上是生活随笔为你收集整理的L2-002 链表去重-团体程序设计天梯赛GPLT的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。