思路: 通过map映射先将原链表处理出来,再通过判重将其分成两部分存储输出。注意测试点1有个坑点(原链表不是一条完成的链表,数据如下:)
(测试点1)输入:
00001 3
00001 1 00002
00002 2 -1
00003 3 00004
(测试点1)输出:
00001 1 00002
00002 2 -1
代码实现:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;int n, b[N], idx, tt, val;
string head, pos, nxt;
map<int, int> vis;
map<string, int> mp;
map<string, string> np;
vector<string> a, ans1, ans2;
int a1[N], a2[N], tt1, tt2, last;//struct node{
// int pos, val, next;
//}b[N];signed main()
{cin >> head >> n;for(int i = 1; i <= n; i ++){cin >> pos >> val >> nxt;mp[pos] = val;np[pos] = nxt;if(pos==head) idx = i;}a.push_back("0");while(tt<n){a.push_back(head);b[++tt] = mp[head];head = np[head];}for(int i = 1; i <= n; i ++){
// cout << a[i] << " \n"[i==n];if(a[i]=="-1"){last = i-1;break;}}if(!last) last = n; //测试点1的坑
// cout << "last: " << last << endl;for(int i = 1; i <= last; i ++){
// cout << b[i] << " \n"[i==n];if(!vis[abs(b[i])]){vis[abs(b[i])] = 1;ans1.push_back(a[i]);a1[tt1++] = b[i];}else{ans2.push_back(a[i]);a2[tt2++] = b[i];}}for(int i = 0; i < tt1; i ++){if(i==tt1-1) cout << ans1[i] << " " << a1[i] << " " << -1 << endl;else cout << ans1[i] << " " << a1[i] << " " << ans1[i+1] << endl;}for(int i = 0; i < tt2; i ++){if(i==tt2-1) cout << ans2[i] << " " << a2[i] << " " << -1 << endl;else cout << ans2[i] << " " << a2[i] << " " << ans2[i+1] << endl;}return 0;
}