1052. Linked List Sorting.md

【PAT A-1052】Linked List Sorting

题意概述

对给出的单链表进行排序。

输入输出格式

输入第 1 行给出结点总个数正整数 N 和第 1 个链表首个结点的地址。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。接下来有 N 行，每行格式为：Address Data Next，其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。

输出格式与输入的格式相同，先输出链表结点总数和排序后链表的首地址，然后输出所有结点的信息。

数据规模

$$N\le {10}^5$$

算法设计

我们依然可以用静态链表的方式存储给出的各个结点信息，以结点地址作为结点在静态链表数组中的下标。为了方便，静态链表数组的元素类型可以是array<gg,2>，负责储存数据域和下一个地址。由于所给的地址是 5 位非负整数，静态链表的长度可以定义成${10}^6$，就可以表示所有的结点。 接着，定义一个vector<gg>lst，由所给链表开始地址处开始遍历整个链表，按遍历顺序将各结点地址储存到 lst 中。利用 sort 函数按要求对 lst 数组进行排序，按格式要求进行结果输出。

注意点

1. 题目给出的结点中可能有不在链表中的无效结点。
2. 输出时结点地址除-1 外要有 5 位数字，不够则在高位补 0。所以地址-1 要进行特判输出。
3. 注意如果给定的初始地址就是-1，即给定的链表是空表的情况，此时只输出一行“0 -1”。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<array<gg, 2>> input(gg(1e6), {-1, -1});
    gg start, ni;
    cin >> ni >> start;
    if (start == -1) {  //为空链表时直接输出0 -1
        cout << "0 -1\n";
        return 0;
    }
    for (gg i = 0; i < ni; ++i) {
        gg address, data, nextA;
        cin >> address >> data >> nextA;
        input[address] = {data, nextA};
    }
    vector<gg> lst;
    while (start != -1) {
        lst.push_back(start);
        start = input[start][1];
    }
    sort(lst.begin(), lst.end(),
         [&input](gg a, gg b) { return input[a][0] < input[b][0]; });
    cout << setfill('0') << lst.size() << " " << setw(5) << lst[0] << "\n";
    for (gg i = 0; i < lst.size() - 1; ++i) {
        cout << setw(5) << lst[i] << " " << input[lst[i]][0] << " " << setw(5)
             << lst[i + 1] << "\n";
    }
    cout << setw(5) << lst.back() << " " << input[lst.back()][0] << " -1\n";
    return 0;
}