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

末蓝、 2023-07-05 14:57 95阅读 0赞

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

![problem][]

### 题目大意 ###

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

### 题目分析 ###

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

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

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

*  地址直接用  i n t int int 类型存储，没必要用  s t r i n g string string，否则无法用上上述存储结构（别跟我说用  m a p map map ，我第一发就是这样超时的）。
 *  格式控制符 “%05d” 表示如果输出的字符少于5位时，在左边补  0 0 0 （默认是补空格）。
 *  删除操作需要用到前驱节点  p r e pre pre 的指针 ， p r e 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]: https://pintia.cn/problem-sets/994805046380707840/problems/994805072641245184
[problem]: https://img-blog.csdnimg.cn/20200217003521661.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/20200217123612847.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20200217155626343.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70