Given a linked list L with integer keys, you need to remove nodes with duplicate absolute key values. That is, for each key K, only the first node with absolute value K is kept. Meanwhile, all removed nodes must be saved in another linked list. For example, given L as 21→-15→-15→-7→15, you should output the deduplicated list 21→-15→-7 and the removed list -15→15.

Input Format:

The first line contains the address of the first node of L and a positive integer N (≤10^5, total number of nodes). A node address is a non-negative 5-digit integer, and null address is represented by -1.

Then N lines follow, each describing a node in the format:

address key next

where address is the node's address, key is an integer with absolute value ≤10^4, and next is the address of the next node.

Output Format:

First output the deduplicated linked list, then output the removed linnked list. Each node occupies a line, printed in the same format as the input.

Sample Input:

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

Sample Output:

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

Analysis:

We use a array nodes to store the value and next pointer for each node, indexed by address.

We use a boolean array seen to record which absolute values have already appeared in the kept list.

We traverse the original list. For each node, if its absolute value has not been seen, we add it to the kept list; otherwise, we add it to the removed list. Then we output the two lists with proper formatting.

Rewrittten Code:

#include <iostream>
#include <cstring>
#include <cmath>

const int MAXN = 100005;
int nodes[MAXN][2]; // nodes[addr][0] = value, nodes[addr][1] = next
bool seen[MAXN];
int kept[MAXN], removed[MAXN];
int keptCount = 0, removedCount = 0;

int main() {
    int start, n;
    scanf("%d%d", &start, &n);
    memset(nodes, -1, sizeof(nodes));
    while (n--) {
        int addr, val, nxt;
        scanf("%d%d%d", &addr, &val, &nxt);
        nodes[addr][0] = val;
        nodes[addr][1] = nxt;
    }
    for (int cur = start; cur != -1; cur = nodes[cur][1]) {
        int absVal = abs(nodes[cur][0]);
        if (!seen[absVal]) {
            kept[keptCount++] = cur;
            seen[absVal] = true;
        } else {
            removed[removedCount++] = cur;
        }
    }
    for (int i = 0; i < keptCount - 1; i++) {
        printf("%05d %d %05d\n", kept[i], nodes[kept[i]][0], kept[i+1]);
    }
    if (keptCount > 0) {
        printf("%05d %d -1\n", kept[keptCount-1], nodes[kept[keptCount-1]][0]);
    }
    if (removedCount > 0) {
        for (int i = 0; i < removedCount - 1; i++) {
            printf("%05d %d %05d\n", removed[i], nodes[removed[i]][0], removed[i+1]);
        }
        printf("%05d %d -1\n", removed[removedCount-1], nodes[removed[removedCount-1]][0]);
    }
    return 0;
}