L2-002 链表去重 - C语言

发布时间：2023/10/11

L2-002 链表去重

题目描述：
C语言解法：
- 1. 数组解法

时间：2021年4月15日
题目来源：团体程序设计天梯赛-练习集

题目描述：

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（ ≤ 10⁵ ，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 ?1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址键值下一个结点

其中地址是该结点的地址，键值是绝对值不超过 10^?4 的整数，下一个结点是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

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

C语言解法：

1. 数组解法

解决问题最好的方法就是不把问题当作问题，所以解决链表最好的方法就是不把链表当作成链表，除非你会用链表。

定义一个 Abs[] 数组，若绝对值 15 存在，则 Abs[15] = 1，否则为 0；

节点 00100 的数字保存到 Number[00100] 中，节点 00100 的下一个节点保存到 Next[00100] 中。

一个一个检查节点，若节点数字对应的 Abs[next] = 1，则将这个节点放入副链表，并将它从主链表中删除；若 Abs[next] = 0，则将之改为 1，并将该节点与上一个节点连接。

最后将两个链表封上，输出。
注意，若没有被删除的节点，那么不输出副链表（第三个测试点）。
注意输出的地址格式。

#include<stdio.h> #include<math.h> int main(){ int Number[100000] = {}, Next[100000] = {}, Abs[100000] = {}; int index, n, i, head, node = -1, next, fhead = -1, fnode; scanf("%d%d", &head, &n); for(i=0; i<n; i++){ scanf("%d", &index); scanf("%d", &Number[index]); scanf("%d", &Next[index]); } next = head; while(next != -1){ if(Abs[abs(Number[next])] == 1){ // next 需删除，转移到副链表 if(fhead == -1){ fhead = next; fnode = next; next = Next[next]; continue; } Next[fnode] = next; fnode = next; // 从主链表中删除 next 节点 Next[node] = Next[next]; }else{ // 节点保留，记录到 Abs[] if(node == -1){ Abs[abs(Number[next])] = 1; node = next; next = Next[next]; continue; } Next[node] = next; Abs[abs(Number[next])] = 1; node = next; } next = Next[next]; } Next[fnode] = -1; Next[node] = -1; // 输出主链表 node = head; while(Next[node] != -1){ printf("%05d %d %05d\n", node, Number[node], Next[node]); node = Next[node]; } printf("%05d %d %d\n", node, Number[node], Next[node]); // 输出副链表 if(fhead == -1){ // 第三个测试点 return 0; } fnode = fhead; while(Next[fnode] != -1){ printf("%05d %d %05d\n", fnode, Number[fnode], Next[fnode]); fnode = Next[fnode]; } printf("%05d %d %d\n", fnode, Number[fnode], Next[fnode]); return 0; }

L2-002 链表去重 - C语言

L2-002 链表去重

题目描述：

C语言解法：

1. 数组解法

相关文章

C/C++开发最新文章

热门教程