【GPLT】L2-002 链表去重
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/88756842
题目描述：
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入描述：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1 来表示。
随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。
输出描述：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854输出样例：
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1解题思路：
创建一个结构体数组node，其中包括当前结点的地址address、当前结点的键值key、下一个结点的地址next、用来排序的num，所有的num都赋初值为2*MAX，因为第一个未被删除的结点的num是0，第一个被删除的结点的num是MAX，这样可以确保没有用到的数据在排序时排在最后。用visited来判断结点是否出现过，用cnt1和cnt2来分别记录未删除的结点数量和删除的结点数量。从头结点开始进行遍历，若该结点的键值的绝对值已经出现过了，则令该结点的num=cnt2+MAX。若该结点还未出现过，则用visited进行标记，并令其num=cnt1。最后根据num来进行升序排列，输出的时候需要注意只有cnt1的最后一个结点和cnt2的最后一个结点的next为-1。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
struct LinkNode
{
int address; //当前结点的地址
int key; //当前的键值
int next; //下一个结点的地址
int num;
}node[MAX];
bool cmp(LinkNode a,LinkNode b)
{
return a.num < b.num;
}
bool visited[MAX];
int main()
{
memset(visited,false,sizeof(visited));
int Head,N;
cin >> Head >> N;
for(int i = 0; i < MAX; i++) //所有node中的num初始化为2*MAX
{
node[i].num = 2*MAX;
}
for(int i = 0; i < N; i++)
{
int temp;
cin >> temp;
node[temp].address = temp;
cin >> node[temp].key >> node[temp].next;
}
int cnt1 = 0, cnt2 = 0; //cnt1用来记录没有删除的结点、cnt2用来记录被删除的结点
for(int i = Head; i != -1; i = node[i].next)
{
if(visited[abs(node[i].key)] == false)
{
visited[abs(node[i].key)] = true;
node[i].num = cnt1;
cnt1++;
}
else
{
node[i].num = MAX + cnt2;
cnt2++;
}
}
sort(node,node+MAX,cmp);
int cnt = cnt1 + cnt2;
for (int i = 0; i < cnt; i++)
{
if(i != cnt1-1 && i != cnt-1)
{
printf("%05d %d %05d\n",node[i].address,node[i].key,node[i+1].address);
}
else
{
printf("%05d %d -1\n",node[i].address,node[i].key);
}
}
return 0;
}腾讯云开发者
