B1075 链表元素分类

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

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N ( $\leq)；以及正整数K (\leq)。结点的地址是 5 位非负整数，NULL 地址用 - 表示。$

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 $[ 区间内的整数； Next 是下一结点的地址。题目保证给出的链表不为空。$

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

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

最终AC代码如下：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int maxn = 100005;
int data[maxn]={0};
int hashTable[maxn];

struct Node{
    string lk;
    int n;
    Node(){
        lk = "";
        n = 0;
    }
};

void init(){
    for(int i=0; i<maxn; i++){
        hashTable[i] = -1;
    }
}

string getStr(int n){
    string s;
    for(int i=0; i<5; i++){
        s.insert(s.begin(), '0' + n%10);
        n /= 10;
    }
    return s;
}

int main(){
    int head, N, K, i, now, n, next;
    string s1, s2;
    Node t;
    vector<Node> ans;
    init();
    cin>>head>>N>>K;
    for(i=0; i<N; i++){
        scanf("%d %d %d", &now, &n, &next);
        data[now] = n;
        hashTable[now] = next;
    }
    next = head;
    while(next!=-1){
        if(data[next]<0){
            t.lk = getStr(next);
            t.n = data[next];
            ans.push_back(t);
        }
        next = hashTable[next];
    }
    next = head;
    while(next!=-1){
        if(data[next]>=0 && data[next]<=K){
            t.lk = getStr(next);
            t.n = data[next];
            ans.push_back(t);
        }
        next = hashTable[next];
    }
    next = head;
    while(next!=-1){
        if(data[next]>K){
            t.lk = getStr(next);
            t.n = data[next];
            ans.push_back(t);
        }
        next = hashTable[next];
    }
    t.lk = "-1";
    t.n = 0;
    ans.push_back(t);
    for(i=0; i<ans.size()-1; i++){
        printf("%s %d %s
", (ans[i].lk).c_str(), ans[i].n, (ans[i+1].lk).c_str());
    }
    return 0;
}

这个代码是最开始写的，虽然AC了但有些地方有些赘余，后参看别人的代码（大神代码链接：https://blog.csdn.net/liuchuo/article/details/78037319），于是重新整理思路写了一遍。如下：

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

struct Node{
    int link, data;
}node[100005];

void toAdd(vector<Node> &ans, vector<Node> vn){
    for(int i=0; i<vn.size(); i++){
        ans.push_back(vn[i]);
    }
}

int main(){
    int head, N, K, i, now;
    Node t;
    vector<Node> vn1, vn2, vn3;
    cin>>head>>N>>K;
    for(i=0; i<N; i++){
        scanf("%d", &now);
        scanf("%d %d", &node[now].data, &node[now].link);
    }
    now = head;
    while(now!=-1){
        t.data = node[now].data;
        t.link = now;
        if(t.data<0){
            vn1.push_back(t);
        }else if(t.data>=0 && t.data<=K){
            vn2.push_back(t);
        }else if(t.data>K){
            vn3.push_back(t);
        }
        now = node[now].link;
    }
    toAdd(vn1, vn2);
    toAdd(vn1, vn3);
    for(i=0; i<vn1.size()-1; i++){
        printf("%05d %d %05d
", vn1[i].link, vn1[i].data, vn1[i+1].link);
    }
    printf("%05d %d -1
", vn1[i].link, vn1[i].data);
    return 0;
}

虽然重写的代码在时间复杂度上并没有显著更快，但是却减少了将近一半的代码数量。反思。主要在于以下两个地方：

一、当数字不足5位时，如何输出5位？

在最开始写的代码中，我将数字转化为5位的字符串，然后再输出，但是更高效的写法是：printf("%05d", int);

printf("%05d %d %05d
", vn1[i].link, vn1[i].data, vn1[i+1].link);

二、分别用三个vector向量暂时存储三个类型的数据，那么一次遍历就可以答案。在输出前，再把三个向量拼接在一起。毕竟，大多数情况，空间是足够用的，但是数据量大时，很容易发生超时。

其它：在算法笔记中晴神也提到过，当地址的范围<10的5次方时，可以采用静态链表的方式，说白了也就是hash映射。