PTA——1075 链表元素分类、1105 链表合并、1110 区块反转

1075 链表元素分类

解决代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v;
    int next;
};
map<int,node> s;
vector<vector<pair<int,int>>> ans(3);
vector<pair<int,int>> w;
int main(){
    int st,n,k;
    cin>>st>>n>>k;
    for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        s[a].v=b;
        s[a].next=c;
    }
    int a=st;
    while(a!=-1){
        if(s[a].v<0) ans[0].push_back({a,s[a].v});
        else if(s[a].v<=k) ans[1].push_back({a,s[a].v});
        else ans[2].push_back({a,s[a].v});
        a=s[a].next;
    }
    for(int j=0;j<3;j++)
        for(int i=0;i<ans[j].size();i++)
            w.push_back(ans[j][i]);
    for(int i=0;i<w.size();i++){
        printf("%05d %d ",w[i].first,w[i].second);
        if(i!=w.size()-1) printf("%05d\n",w[i+1].first);
        else cout<<-1<<endl;
    }
    return 0;
}

1105 链表合并

解决代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v;
    int next;
};
map<int,node> l;
vector<pair<int,int>> l1,l2,l3;
int main(){
    int s1,s2,n;
    cin>>s1>>s2>>n;
    while(n--){
        int a,b,c;
        cin>>a>>b>>c;
        l[a].v=b;
        l[a].next=c;
    }
    int x1=s1,x2=s2;
    while(x1!=-1){
        l1.push_back({x1,l[x1].v});
        x1=l[x1].next;
    }
    while(x2!=-1){
        l2.push_back({x2,l[x2].v});
        x2=l[x2].next;
    }
    if(l1.size()<l2.size()){
        swap(l1,l2);
    }
    reverse(l2.begin(),l2.end());
    int cnt=0;
    for(int i=1;i<=l1.size();i++){
        l3.push_back(l1[i-1]);
        if(cnt<l2.size()&&i%2==0) l3.push_back(l2[cnt++]);
    }
    for(int i=0;i<l3.size();i++){
        printf("%05d %d ",l3[i].first,l3[i].second);
        if(i!=l3.size()-1) printf("%05d\n",l3[i+1].first);
        else cout<<"-1"<<endl;
    }
    return 0;
}

1110 区块反转

解决代码

#include<bits/stdc++.h>
using namespace std;
struct no{
    int v;
    int next;
};
map<int,no> p;
int main(){
    int st,n,k;
    cin>>st>>n>>k;
    while(n--){
        int a,b,c;
        cin>>a>>b>>c;
        p[a].v=b;
        p[a].next=c;
    }
    vector<pair<int,int>> l,ans;
    int x=st;
    while(x!=-1){
        l.push_back({x,p[x].v});
        x=p[x].next;
    }
    n=l.size();
    if(n%k!=0){
        for(int i=n/k*k;i<n;i++){
            ans.push_back(l[i]);
        }
        n-=n%k;
    }
    for(int i=n/k-1;i>=0;i--){
        for(int j=i*k;j<i*k+k;j++){
            ans.push_back(l[j]);
        }
    }
    for(int i=0;i<ans.size();i++){
        printf("%05d %d ",ans[i].first,ans[i].second);
        if(i!=ans.size()-1) printf("%05d\n",ans[i+1].first);
        else printf("-1\n");
    }
    return 0;
}

总结

这三道题换汤不换药，总结下来就是首先利用结构体存储节点，利用map存储地址，将地址下标映射到结点。然后用利用头结点的地址将链表串起来，存进vector中，这里每个节点的前后关系就是他们在数组中的位置。
所以存进vector时不用考虑结点的next值了，这只在得到链表时有用。
最后根据题意按照输出次序将结点存进另一个vector中，由于链表中结点前后关系就是链表的关系，因此遍历这个vector即可，遍历即按照链表顺序输出。