题目描述

给定一个链表，对value值进行升序排序

（好像：PAT描述中如果是increasing，就好像不会有相等的情况，nondecreasing则会出现相等的情况

样例

5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345

output
5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

算法1

遍历+排序 $O(nlgn)$

遍历链表为$O(n)$，排序在 $O(nlgn)$。

C++ 代码

 #include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct node {
    int ad, val, ne;
}arr[N];

int n, root;

bool cmp(node & a, node & b) {
    return a.val < b.val;
}
int main() {

    cin >> n >> root;
    for(int i = 0; i < n; ++ i) {
        int ad, val, ne;
        cin >> ad >> val >> ne;
        arr[ad] = {ad, val, ne};
    } 
    vector<node> v;
    while (root != -1) { // 存在不是链表上的点，卡
        v.push_back(arr[root]);
        root = arr[root].ne;
    }

    sort(v.begin(), v.end(), cmp);

    if (v.size() == 0) { // 链表为空，PAT最后一个点
        puts("0 -1");
        return 0;
    }

    printf("%d %05d\n", v.size(), v[0].ad); // 啊，root也有前导0啊，PAT倒数第二个卡点
    // cout << v.size() << " " << v[0].ad; // 这里跪了好久, T...T
    for (int i = 0; i < v.size(); ++ i) {
        if (i != v.size() - 1)
            printf("%05d %d %05d\n", v[i].ad, v[i].val, v[i+1].ad); // 常规前导0，卡
        else 
            printf("%05d %d -1\n", v[i].ad, v[i].val);
    }
}