L2-002. 链表去重

本题要求:

给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。

输入格式：

输入第一行包含链表第一个结点的地址、以及结点个数N（<= 105 的正整数）。结点地址是一个非负的5位整数，NULL指针用-1表示。 随后N行，每行按下列格式给出一个结点的信息： Address Key Next 其中Address是结点的地址，Key是绝对值不超过104的整数，Next是下一个结点的地址。

输出格式：

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

输入样例：

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

解题思路 :

1. 用数组下标记录地址。 2. Node类来记录当前key和next的地址。 3. 用number数组来记录出现次数，大于1的时候则移除到第二个表。

代码 :

#include<iostream> #include<vector> #include<cstdio> using namespace std; struct Node{ int key; int next; }; int main() { Node num[100001] = {0}; int number[10001] = {0}; char temp[10]; int head, n; int head2 = -1; int tail = -1; scanf("%d%d", &head, &n); int address; for (int i = 0; i < n; i++) { scanf("%d", &address); scanf("%d%d", &num[address].key, &num[address].next); } int i = head, j = -1, k; while (i != -1) { if (number[abs(num[i].key)] == 0) { number[abs(num[i].key)] = 1; j = i; i = num[i].next; } else { if (j == -1) { head = num[i].next; } else { num[j].next = num[i].next; } k = num[i].next; num[i].next = -1; if (head2 == -1) { head2 = i; tail = i; } i = k; break; } } while (i != -1) { if (number[abs(num[i].key)] == 0) { number[abs(num[i].key)] = 1; j = i; i = num[i].next; } else { num[j].next = num[i].next; k = num[i].next; num[i].next = -1; num[tail].next = i; tail = i; i = k; } } for (i = head; i != -1; i = num[i].next) { printf("d", i); cout << " " << num[i].key << " "; if (num[i].next != -1) { printf("d", num[i].next); } else { cout << num[i].next; } cout << endl; } for (i = head2; i != -1; i = num[i].next) { printf("d", i); cout << " " << num[i].key << " "; if (num[i].next != -1) { printf("d", num[i].next); } else { cout << num[i].next; } cout << endl; } return 0; }