刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
1.链表去重
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
时间限制：5000
内存限制：65536
输入
输入在第一行给出 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
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
时间限制：5000
内存限制：65536
输入
输入在第一行给出 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
使用微信搜索喵呜刷题，轻松应对考试！
答案：
解析：
为了解决这个问题，我们可以按照以下步骤操作：
- 创建一个空的哈希表来存储已经遇到的绝对值。
- 创建一个空链表来保存被删除的节点。
- 遍历给定的链表。对于每个节点，执行以下操作：
- 获取节点的键值并取其绝对值。
- 检查该绝对值是否已在哈希表中。
- 如果不在哈希表中，将该绝对值添加到哈希表，并将节点添加到保留的链表中。
- 如果已在哈希表中，将节点添加到被删除的链表中。
- 输出保留的链表和被删除的链表。
注意：在遍历链表时，需要同时更新节点的下一个节点的地址，以确保链表的完整性。此外，需要注意空地址NULL的处理，题目中已给出空地址用-1表示。在添加节点到链表时，如果遇到一个空地址，直接跳过该节点。
具体实现时，可以使用数组或哈希表来模拟哈希表的功能。由于题目中结点的地址是非负的5位整数，可以使用一个大小为100000的数组来存储已遇到的绝对值，其中数组索引代表键值，数组元素的值代表该键值是否已遇到（0代表未遇到，1代表已遇到）。这样可以在O(1)的时间复杂度内检查一个键值是否已遇到。
对于输出部分，按照题目要求的格式输出保留的链表和被删除的链表即可。
创作类型：
原创
本文链接：1.链表去重给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
