PAT-A 真题 – 1097 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.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive $N$ ( $\leq 1 0^{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 $1 0^{4}$ , and Next is the position of the next node.

Output Specification:

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.

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

题目大意：给定链表，去重。绝对值一样的数据也算重复

这道题按照题意模拟就行了。注意如果没有删除的元素，第二个链表什么也不要输出！否则第三个测试点（测试点2）无法通过。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef struct{
  int data, next;
} node;

const int MAXN = 100000;
node L[MAXN];
vector<node> R;
int pos[MAXN] = {0};  

int main(){
  int head, cnt;
  cin >> head >> cnt;
  //读取List 
  for(int i = 0; i < cnt; i++){
    int addr;
    cin >> addr;
    cin >> L[addr].data >> L[addr].next;
  }
  //遍历去重 
  for(int p = head; p != -1;){
    pos[  abs( L[p].data ) ] = 1;  //标记这个key已经有啦 
    if(p == head) printf("%05d %d ", p, L[p].data);  //第一个节点直接输出就好了 
    else printf("%05d\n%05d %d ", p, p, L[p].data);  //往后的节点要先输出前一个节点的next 
    int next_p = L[p].next;  //下一个节点 
    while(  next_p != -1 &&         //只要没到达末尾 
        pos[ abs( L[next_p].data ) ]  //并且这个key访问过 
      ){
      R.push_back({L[next_p].data, next_p});  //把这个重复的节点放到vector中  
      next_p = L[next_p].next;  //下一个节点 
    }
    p = next_p;
  }
  cout << -1 << endl;
  for(int i = 0; i < R.size(); i++){
    if(i == 0) printf("%05d %d ", R[i].next, R[i].data);
    else printf("%05d\n%05d %d ", R[i].next, R[i].next, R[i].data);
  }
  if(R.size()) cout << -1;
  return 0;
}

斐斐のBlog