L2-002 链表去重 - C语言
L2-002 链表去重
- 题目描述：
- C语言解法：
- 1. 数组解法
时间：2021年4月15日
题目来源：团体程序设计天梯赛-练习集
题目描述：
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（ ≤ 105 ，为结点总数 ）。一个结点的地址是非负的 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;
}