[数据结构与算法]PAT1097 Deduplication on a Linked List（链表）

原题

题目大意及思路

• 题目大意：给了一个单链表，输出两个链表，一个输出的是第一次出现某个绝对值的链表，另一个是该绝对值再次输出的链表（均按原链表的顺序输出）
  在存储下所有结点信息后进行对链表的遍历，用set来查重，将其分成两个数组输出。

代码

#include<iostream>
#include<map>
#include<unordered_set>
#include<vector>
#include<cmath>
using namespace std;
struct node{
	int add,value,next;
};
int main(){
	int add,n;
	cin>>add>>n;
	map<int,node> m;
	unordered_set<int> absv;
	vector<int> ans1,ans2;
	for(int i=0;i<n;i++){
		int nowadd,nowvalue,nownext;
		cin>>nowadd>>nowvalue>>nownext;
		node now={nowadd,nowvalue,nownext};
		m[nowadd]=now;
	}
	for(;add!=-1;add=m[add].next){
		if(absv.find(abs(m[add].value))!=absv.end()) ans2.push_back(add);
		else{
			ans1.push_back(add);
			absv.insert(abs(m[add].value));
		} 
	}
	for(int i=0;i<ans1.size();i++){
        printf("%05d %d ",ans1[i],m[ans1[i]].value);
        if(i==ans1.size()-1) printf("-1\n");
        else printf("%05d\n",ans1[i+1]);
    }
    for(int i=0;i<ans2.size();i++){
        printf("%05d %d ",ans2[i],m[ans2[i]].value);
        if(i==ans2.size()-1) printf("-1\n");
        else printf("%05d\n",ans2[i+1]);
    }	
	return 0;
}

运行截图

收获

一种方法不行就另一种！