C++ 链表去重：删除绝对值重复的节点

#include #include <unordered_map>

using namespace std;

const int N = 100010;

struct ListNode { int val, next; } e[N];

int main() { int head, n; cin >> head >> n; for (int i = 0; i < n; i++) { int address; cin >> address; cin >> e[address].val >> e[address].next; }

// 遍历链表，记录每个元素出现的次数
unordered_map<int, int> cnt;
for (int i = head; i != -1; i = e[i].next) {
    int t = abs(e[i].val);
    cnt[t]++;
}

// 找到第一个没有重复项的结点
while (head != -1 && cnt[abs(e[head].val)] > 1) head = e[head].next;

// 新建两个链表，一个存储去重后的链表，一个存储被删除的链表
int p1 = -1, p2 = -1, q1 = -1, q2 = -1;
for (int i = head; i != -1; i = e[i].next) {
    int t = abs(e[i].val);
    if (cnt[t] == 1) {
        if (p1 == -1) p1 = i, p2 = i;
        else p2 = e[p2].next = i;
    } else {
        if (q1 == -1) q1 = i, q2 = i;
        else q2 = e[q2].next = i;
    }
}

// 将两个链表输出
for (int i = p1; i != -1; i = e[i].next) {
    printf('%05d %d ', i, e[i].val);
    if (e[i].next == -1) puts('-1');
    else printf('%05d

', e[i].next); }

for (int i = q1; i != -1; i = e[i].next) {
    printf('%05d %d ', i, e[i].val);
    if (e[i].next == -1) puts('-1');
    else printf('%05d

', e[i].next); }

return 0;

}