1-10 链表去重 (20分)

给定一个带整数键值的链表 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

这道题卡了我好久，呼~

我刚开始的思路就很。。。简单。就 先用数组把他们存下来，然后再排序到链表里，然后再for循环，两层循环，删除。

然后我就写，然后样例过了，然后有俩超时，我就想，是不是从数组往链表排序那太费事了。然后就想着不行就输入也用链表吧，最后我忘过没过了，可能还是超时？因为现在那个题目集已经结束了，我也不能再提交看看是什么情况，应该没AC。然后我就看网上的一个办法，特别厉害。然后用那个办法写了一下，过了。然后第二天我自己又用链表写了一下，这次第一次提交，有两个点过不去，然后我突然发现那个key的值是小于等于10000。然后数组长度加了个1，就AC了。呼~

思路：总而言之学到了几个东西：

删除元素，不非得用两层for循环。建立一个数组，先都设置为0，索引就是这个数的值。具体算法是：如果循环到一个数，他还没有出现过，就把他置为1，表示这个数出现过了。循环到下一个相同的数，发现数组里对应的值是1，就把他删除。复杂度直接成了O(N)了。就是直接可以把那个五位数的地址，当成一个数组的索引。具体看代码把。不用管下一个数的地址，删除完之后，这个节点存的下一个地址直接输出下一个地点的对应的地址。

代码没有过的

#include <iostream> #include <cstdlib> #include <cmath> #include <cstdio> #define nullptr NULL using namespace std; typedef struct Node *List; struct Node { int thisAddress; int key; int nextAddress; List next; }; int firstAddress, N; void Read(List L); void Sort(List L, List L0); void Print(List L); List DelRepeat(List L); int main() { List L0 = (List)malloc(sizeof(struct Node)); L0->next = nullptr; Read(L0); List L = (List)malloc(sizeof(struct Node)); L->next = nullptr; //排序到链表 Sort(L, L0); List outL = DelRepeat(L); Print(L); Print(outL); } void Read(List L) { List temp = L; cin >> firstAddress >> N; List currNode; for (int i = 0; i < N; i++) { currNode = (List)malloc(sizeof(struct Node)); cin >> currNode->thisAddress >> currNode->key >> currNode->nextAddress; temp->next = currNode; temp = temp->next; temp->next = nullptr; } } void Sort(List L, List L0) { List temp = L; List temp_next = NULL; List temp_pre = L0; int pre = firstAddress; List tempL0; do { tempL0 = L0->next; temp_pre = L0; while (tempL0) { if (tempL0->thisAddress == pre) { temp_pre->next = tempL0->next; //tempL0删除 temp->next = tempL0; temp = temp->next; temp->next = nullptr; pre = temp->nextAddress; //temp添加 break; } temp_pre = tempL0; tempL0 = tempL0->next; } } while (pre != -1); } void Print(List L) { List temp = L->next; while (temp) { if (temp->nextAddress != -1) printf("d %d d\n", temp->thisAddress, temp->key, temp->nextAddress); else printf("d %d -1\n", temp->thisAddress, temp->key); temp = temp->next; } } List DelRepeat(List L) { List DelL = (List)malloc(sizeof(struct Node)); DelL->next = nullptr; List tempL = L->next, tempDelL = DelL; //debug2 这刚开始写成L了 while (tempL) { int absnum = abs(tempL->key); List pre = tempL; List tempL_2 = tempL->next; while (tempL_2) { if (abs(tempL_2->key) == absnum) { tempDelL->next = tempL_2; tempDelL->nextAddress = tempL_2->thisAddress; // tempL_2 = tempL_2->next; tempDelL->next->next = nullptr; tempDelL->next->nextAddress = -1; // tempDelL = tempDelL->next; //debug1这没有这个语句 pre->next = tempL_2; //这有个段错误 if (tempL_2 == nullptr) pre->nextAddress = -1; else { pre->nextAddress = tempL_2->thisAddress; // } } else { pre = tempL_2; tempL_2 = tempL_2->next; } } tempL = tempL->next; } return DelL; }

代码过了的_按照大佬的代码写的

#include <iostream> #include <cmath> #include <algorithm> #include <cstdio> using namespace std; #define MaxN 100000 struct Node { int address; int key; int next; int num; } Arr[MaxN]; bool isExist[MaxN]; bool cmp(Node n1, Node n2) { return n1.num < n2.num; } int main() { for (int i = 0; i < MaxN; i++) { Arr[i].num = 2 * MaxN; } int n, first, pre; cin >> first >> n; pre = first; int a; for (int i = 0; i < n && pre != -1; i++) { scanf("%d", &a); scanf("%d %d", &Arr[a].key, &Arr[a].next); Arr[a].address = a; pre = a; } int cnt1 = 0, cnt2 = 0; for (int i = first; i != -1; i = Arr[i].next) { if (!isExist[abs(Arr[i].key)]) { isExist[abs(Arr[i].key)] = true; Arr[i].num = cnt1++; } else { Arr[i].num = MaxN + cnt2++; } } sort(Arr, Arr + MaxN, cmp); for (int i = 0; i < cnt1 + cnt2; i++) { if (i != cnt1 - 1 && i != cnt1 + cnt2 - 1) { printf("d %d d\n", Arr[i].address, Arr[i].key, Arr[i + 1].address); } else { printf("d %d -1\n", Arr[i].address, Arr[i].key); } } }

代码过了的_链表写的

#include <cstdio> #include <cstdlib> #include <cmath> using namespace std; typedef struct Node *List; struct Node { int address; int key; int nextaddress; List next; }; int firstAddress, N; bool isExited[10001]; //默认false List Read(); List Sort(List L); List DelRepeat(List L); List PrintL(List L); int main() { List rawL = Read(); List sortedL = Sort(rawL); List deledL = DelRepeat(sortedL); PrintL(sortedL); PrintL(deledL); } List Read() { scanf("%d %d", &firstAddress, &N); List L = (List)malloc(sizeof(Node)), tmp, s; L->next = NULL; tmp = L; for (int i = 0; i < N; i++) { s = (List)malloc(sizeof(Node)); scanf("%d %d %d", &(s->address), &(s->key), &(s->nextaddress)); s->next = NULL; tmp->next = s; tmp = s; } return L; } List Sort(List L) { List L1 = L, L2 = (List)malloc(sizeof(Node)), t1, pre_t1; //L1 没有排序呢，L2 排好的 List t2 = L2; L2->next = NULL; int pre = firstAddress; do { t1 = L1->next; pre_t1 = L1; while (t1) { if (t1->address == pre) { t2->next = t1; t2 = t2->next; pre_t1->next = t1->next; t2->next = NULL; pre = t2->nextaddress; break; } pre_t1 = t1; t1 = t1->next; } } while (pre != -1); return L2; } List DelRepeat(List L) { List L1 = L, L2 = (List)malloc(sizeof(Node)), t1 = L1->next, t2 = L2, pre_t1 = L1; //L1 原来的除重剩下的，L2被删除的 L2->next = NULL; while (t1) { if (!isExited[abs(t1->key)]) { isExited[abs(t1->key)] = true; pre_t1 = t1; t1 = t1->next; } else { t2->next = t1; pre_t1->next = t1->next; //old del t1 = t1->next; //t1 更新,pre_t1 没有变化 t2 = t2->next; //t2 更新 t2->next = NULL; } } return L2; } List PrintL(List L) { List tmp = L->next; while(tmp) { if (tmp->next) printf("d %d d\n", tmp->address, tmp->key, tmp->next->address); else printf("d %d -1\n", tmp->address, tmp->key); tmp=tmp->next; } }

呼，终于把三四周的卡到我的题，都写了一遍。