[PAT解题报告] Deduplication on a Linked List
PAT的链表题，表示链表的方法很诡异，类似的表示还有1052，
1074。也不难，本题给定一个存储整数的链表，只保存每种绝对值第一次出现的节点，同一个绝对值第二次及以后的出现都扔掉，保留的节点和扔掉的节点分别组成两个小链表。
链表存放整数的绝对值不超过10000，所以可以用bool数组或者bitmap保存某个绝对值在之前是否出现过。
不知道有没有极端情况，输入的链表就是个空的……
总之，我们可以先新建立两个表头h1, h2 和表尾t1,
t2，初始都是空的，表示我们最后保留的链表和过滤掉的链表。链表的优势就是对每个节点可以单独折腾……
我们对原始链表里每个节点，可以通过我们那个bool数组判断这个绝对值是否出现过，如果出现过就接到第二个链表末尾，否则就放到第一个链表的末尾。接在链表末尾的操作注意和用指针差不多，注意是否是第一个表头节点，同时别忘更新最后一个元素的地址，因为每次都要接在最后一个元素后面……当然接在前面再翻转一次也是可以的。
最后输出也要注意链表为空的情况，还有注意最后一个位置的next是-1。
难度不大，就是每种细节的处理而已。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int Next[1000000];
int a[1000000];
bool mark[10005];
int main() {
int n;
int head;
for (scanf("%d%d",&head,&n);n;--n) {
int x;
scanf("%d",&x);
scanf("%d%d",a + x, Next + x);
}
int h1 = -1, h2 = -1, t1 = -1, t2 = -1;
for (; head >= 0; head = Next[head]) {
int x = (a[head] >= 0)?a[head]:(-a[head]);
if (mark[x]) {
if (t2 < 0) {
h2 = t2 = head;
}
else {
t2 = Next[t2] = head;
}
}
else {
mark[x] = true;
if (t1 < 0) {
h1 = t1 = head;
}
else {
t1 = Next[t1] = head;
}
}
}
if (t1 >= 0) {
Next[t1] = -1;
for (head = h1; head >= 0; head = Next[head]) {
printf("%05d %d", head, a[head]);
if (Next[head] >= 0) {
printf(" %05d\n", Next[head]);
}
else {
puts(" -1");
}
}
}
if (t2 >= 0) {
Next[t2] = -1;
for (head = h2; head >= 0; head = Next[head]) {
printf("%05d %d", head, a[head]);
if (Next[head] >= 0) {
printf(" %05d\n", Next[head]);
}
else {
puts(" -1");
}
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1097
投递大疆等公司10个岗位
查看30道真题和解析