[PAT A1097]Deduplication on a Linked List_综合

[PAT A1097]Deduplication on a Linked List

题目描述

Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

输入格式

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (≤10?5??) which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by ?1.

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

Address Key Next

where Address is the position of the node, Key is an integer of which absolute value is no more than 10?4??, and Next is the position of the next node.

输出格式

For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

输入样例

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

解析

题目大意就是输入n个结点和起始地址，对于从起始地址开始的链表，我们要将它重复的元素剔出来（注意这道题目只要是绝对值相同就相当于重复）原链表保留第一次出现的重复元素，新链表保留之后出现的重复元素，例如-7->-15->15->-15->21。其中-15，15一共出现了三次，这里只保留第一次出现的-15，所以链表为-7->-15->21。剔出去的链表为15->-15
同理，这里需要注意的是，不见得每个结点都是有效的，对于无效结点，我们不做考虑。
我这里使用了hash散列的思想；并使用了vector去存储两个链表，相比于晴神和柳神的代码，算不上最优，但感觉是最容易看懂的。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node {int addr, data, next, cnt; //某个结点的地址，存储元素和下一个元素的地址
};
node nodes[100010];
bool cmp(node n1, node n2) {return n1.cnt < n2.cnt; //按照链表顺序排列
}
bool hashTable[100000] = { false };//初始化
int main()
{int start, n, cnt = 0;vector<node> v1, v2;scanf("%d%d", &start, &n);for (int i = 0; i < 100010; i++) nodes[i].cnt = 100009;for (int i = 0; i < n; i++) {int addr, data, next;scanf("%d%d%d", &addr, &data, &next);nodes[addr] = { addr,data,next,100009 };//注意这里100009不可以省略！如果省略它会自动赋值0，抹掉了前面赋值的100009}while (start != -1) {nodes[start].cnt = cnt++;start = nodes[start].next;}//计算有效结点个数并为它们按顺序赋值，以便sort函数能够实现排序sort(nodes, nodes + 100010, cmp);for (int i = 0; i < cnt; i++) {if (!hashTable[abs(nodes[i].data)]) { //如果之前出现过，那么push到v1里面，并使得hash表该位置为truev1.push_back(nodes[i]);hashTable[abs(nodes[i].data)] = true;}else v2.push_back(nodes[i]); //否则push到v2里面}for (int i = 0; i < v1.size(); i++) {printf("%05d %d ", v1[i].addr, v1[i].data);if (i != v1.size() - 1) printf("%05d\n", v1[i + 1].addr);else printf("-1\n");}for (int i = 0; i < v2.size(); i++) {printf("%05d %d ", v2[i].addr, v2[i].data);if (i != v2.size() - 1) printf("%05d\n", v2[i + 1].addr);else printf("-1\n");}return 0;
}