给定一个带整数键值的链表 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
思路：
很多办法都可以实现，我选择数组模拟动态内存，先建立一个链表再遍历，时间复杂度是o(n)，格式控制还是printf好用。
#include<iostream> #include<cstdio> #include<cmath> #define null -1 using namespace std; typedef struct node { int val; unsigned int next; }node; node store[100001];//开辟一片模拟内存 int flag[10001];//标记结点 int main() { int num, startm;//p标记当前节点 cin >> startm >> num; for (int i = 0; i < num; i++) { int now, val, next; cin >> now >> val >> next; store[now].val = val; store[now].next = next; }//链表构建完成 int p1=startm,starts=null; int p2 = 100000,pre; bool k = true; while (p1 != null) { if (flag[abs(store[p1].val)] != 0) { store[pre].next = store[p1].next; store[p2].next = p1; store[p1].next = null; p2 = p1; if (k) { k = false; starts = p2; } p1 = store[pre].next; } else { flag[abs(store[p1].val)] = 1; pre = p1; p1 = store[p1].next; } }//链表查重完成 p1 = startm; while (p1 != null) { if(store[p1].next!=null) printf("%05d %d %05dn",p1, store[p1].val, store[p1].next); else printf("%05d %d %dn", p1, store[p1].val, store[p1].next); p1 = store[p1].next; } p1 = starts; while (p1 != null) { if (store[p1].next != null) printf("%05d %d %05dn", p1, store[p1].val, store[p1].next); else printf("%05d %d %dn", p1, store[p1].val, store[p1].next); p1 = store[p1].next; } return 0; }
到此这篇关于c++ 实现l2-002 链表去重的文章就介绍到这了,更多相关c++ 链表去重内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！
需要了解更多c/c++开发分享C++ 实现L2-002 链表去重，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/644754.html