1097 Deduplication on a Linked List (25 point(s))

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 (≤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.

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

题目大意：给一个链表，去掉绝对值相等的结点，先输出删除后的链表，再输出删除了的链表。

分析：采用结构体存储单链表结点，在遍历单链表L过程标记一下，并将删除后的链表保存在ans中，删除了的结点保存在rmove中，然后分别输出ans和rmove即可。

完整代码：

#include<bits/stdc++.h> using namespace std; struct node{ int add; int val; int next; }L[100010],ans[100010],rmove[100010]; int vis[100010];//标记结点的绝对值是否相等； int main(){ int begin,n; cin>>begin>>n; for(int i=0;i<n;i++){ int add,val,next; scanf("%d%d%d",&add,&val,&next); L[add].add=add,L[add].val=val,L[add].next=next; } int cnt1=0,cnt2=0;//分别记录保留的单链表长度和删除的单链表长度 for(int i=begin;i!=-1;i=L[i].next){ if(!vis[abs(L[i].val)]){ vis[abs(L[i].val)]=1; ans[cnt1++]=L[i]; }else{ rmove[cnt2++]=L[i]; } } for(int i=0;i<cnt1-1;i++) printf("%05d %d %05d\n",ans[i].add,ans[i].val,ans[i+1].add); // 这里只能用ans[i+1].add,不能用ans[i].next进行输出下一个结点首地址 printf("%05d %d -1\n",ans[cnt1-1].add,ans[cnt1-1].val); if(cnt2>0){//有删除则输出 for(int i=0;i<cnt2-1;i++) printf("%05d %d %05d\n",rmove[i].add,rmove[i].val,rmove[i+1].add); printf("%05d %d -1\n",rmove[cnt2-1].add,rmove[cnt2-1].val); } return 0; }