1052 Linked List Sorting (巨坑题）

本文介绍: 题意：以address,val,next_address的形式给定一个链表，同时给定头节点的address，求将该链表排序后的形式。坑点二：没想到吧，给定的链表还可能为空！这种情况下，我们只需要输出0与头结点就行了。坑点一：有的结点不在该链表上，需要遍历一遍链表排除掉。（可以用哈希表存储链表）pat拿分简单，但是拿要高分确实难。

题意：以address,val,next_address的形式给定一个链表，同时给定头节点的address，求将该链表排序后的形式。

pat拿分简单，但是拿要高分确实难。。

坑点一：有的结点不在该链表上，需要遍历一遍链表排除掉。（可以用哈希表存储链表）

坑点二：没想到吧，给定的链表还可能为空！这种情况下，我们只需要输出0与头结点就行了。

#include<bits/stdc++.h>
using namespace std;
struct node{
    string address;
    int val;
    string next;
};
int main(){
    vector<node>res;
    map<string,node>mp;
    int n;cin>>n;
    string head;
    cin>>head;
    for(int i=0;i<n;i++){
        string nod,next;
        int val;
        cin>>nod>>val>>next;
        mp[nod]={nod,val,next};
    }
    while(mp.count(head)){
        res.push_back({head,mp[head].val});
        head=mp[head].next;
    }
    sort(res.begin(),res.end(),[](auto&a,auto&b){
        return a.val<b.val;
    });
    if(res.size()==0){
        cout<<0<<' '<<head;return 0;
        // cout<<0;return 0;
    }
    n=res.size();
    for(int i=0;i<n-1;i++){
        res[i].next=res[i+1].address;
    }
    res[n-1].next="-1";
    cout<<n<<' '<<res[0].address<<endl;
    for(int i=0;i<n;i++){
        cout<<res[i].address<<' '<<res[i].val<<' '<<res[i].next<<endl;
    }
    
}