[数据结构与算法]PAT B1075链表元素分类

题目连接：https://pintia.cn/problem-sets/994805260223102976/problems/994805262953594880

输入样例：

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例：

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

思路见代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

typedef struct Node{
    int address;
    int data;
    int next;
}ND;

int main()
{
    int addr,M,K,num=0,n=0,feinum=0,Knum=0;//Knum:0=<data<=K的节点数目
    //feinum:data>K的节点数目,n:读入的节点中在链表中的数目
    scanf("%d %d %d",&addr,&M,&K);
    vector<ND> nd(M);
    vector<int> last(M,0),tmp1(M,0),tmp2(M,0);//last记录最终排序结果
    //tmp1记录0~K的节点排序，tmp2记录大于K的节点排序
    for(int i=0;i<M;i++) scanf("%d %d %d",&nd[i].address,&nd[i].data,&nd[i].next);
        for(int j=0;addr!=-1;j++){
            if(nd[j].address==addr){
                addr=nd[j].next;
                if(nd[j].data<0) last[num++]=j;
                else if(nd[j].data>=0 && nd[j].data<=K) tmp1[Knum++]=j;
                else if(nd[j].data>K) tmp2[feinum++]=j;
                n++;
                break;
            }
        }
    for(int i=0;i<Knum;i++) last[num++]=tmp1[i];
    for(int i=0;i<feinum;i++) last[num++]=tmp2[i];  
    for(int i=0;i<n-1;i++)
        printf("%05d %d %05d\n",nd[last[i]].address,nd[last[i]].data,nd[last[i+1]].address);
    printf("%05d %d -1\n",nd[last[n-1]].address,nd[last[n-1]].data);
    return 0;
}

节点5数据量较大，O(n2)的时间复杂度会超时。下面是优化：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

typedef struct Node{
    int data;
    int next;
}ND;

int main()
{
    int addr,M,K,num=0,n=0,feinum=0,Knum=0;
    scanf("%d %d %d",&addr,&M,&K);
    vector<ND> nd(100000);
    vector<int> last(M,0),tmp1(M,0),tmp2(M,0);
    for(int i=0;i<M;i++){
        scanf("%d",&n);
        scanf("%d %d",&nd[n].data,&nd[n].next);
    }
    n=0;
    for(int j=addr;j!=-1;j=nd[j].next){
        if(nd[j].data<0) last[num++]=j;
        else if(nd[j].data>=0 && nd[j].data<=K) tmp1[Knum++]=j;
        else if(nd[j].data>K) tmp2[feinum++]=j;
        n++;
    }
    for(int i=0;i<Knum;i++) last[num++]=tmp1[i];
    for(int i=0;i<feinum;i++) last[num++]=tmp2[i];  
    for(int i=0;i<n-1;i++)
        printf("%05d %d %05d\n",last[i],nd[last[i]].data,last[i+1]);
    printf("%05d %d -1\n",last[n-1],nd[last[n-1]].data);
    return 0;
}