首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13151

链表去重 给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须…

链表去重

给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。

例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。

时间限制:5000,内存限制:65536

输入

输入在第一行给出 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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;unordered_set&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;iomanip&gt; using namespace std; struct Node {     int address;     int key;     int next; }; int main() {     int start, n;     cin &gt;&gt; start &gt;&gt; n;          // 用数组存储所有节点,索引为节点地址     vector&lt;Node&gt; nodes(100000);     for (int i = 0; i &lt; n; i++) {         int addr, key, next;         cin &gt;&gt; addr &gt;&gt; key &gt;&gt; next;         nodes[addr] = {addr, key, next};     }          unordered_set&lt;int&gt; seen;  // 记录已出现过的绝对值     vector&lt;Node&gt; kept;       // 保留链表的节点     vector&lt;Node&gt; removed;    // 删除链表的节点          int current = start;     while (current != -1) {         int absKey = abs(nodes[current].key);         if (seen.find(absKey) == seen.end()) {             seen.insert(absKey);             kept.push_back(nodes[current]);         } else {             removed.push_back(nodes[current]);         }         current = nodes[current].next;     }          // 输出保留链表     for (int i = 0; i &lt; kept.size(); i++) {         printf("%05d %d ", kept[i].address, kept[i].key);         if (i &lt; kept.size() - 1) {             printf("%05d\n", kept[i + 1].address);         } else {             printf("-1\n");         }     }          // 输出删除链表     for (int i = 0; i &lt; removed.size(); i++) {         printf("%05d %d ", removed[i].address, removed[i].key);         if (i &lt; removed.size() - 1) {             printf("%05d\n", removed[i + 1].address);         } else {             printf("-1\n");         }     }          return 0; }</pre>
这道题暂未补解析。