[数据结构与算法]【PAT甲级】1052 Linked List Sorting

?个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1052 Linked List Sorting (pintia.cn)
🔑中文翻译：链表排序
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
??如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1052 Linked List Sorting

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (<10⁵) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by ?1.

Then N lines follow, each describes a node in the format:

Address Key Next

where Address is the address of the node in memory, Key is an integer in [?10⁵,10⁵], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

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

Sample Output:

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

题意

第一行首先包含一个整数 $N$，表示总节点数量，然后包含链表头节点的地址。

接下来 $N$ 行，每行描述一个节点的信息，格式如下：

Address Key Next

其中 Address 是节点地址，Key 值是一个整数，Next 是下一个节点的地址。

地址都是 5 位正整数，可能有前导 0 。

保证各节点的 Key 值互不相同，且链表中不存在环形结构。

第一行首先输出一个整数表示链表的总节点数量，然后输出排序后的链表头节点地址。

接下来若干行，从头节点开始，依次输出每个节点的信息，格式与输入相同。

注意：

1. 本题中可能包含不在链表中的节点，这些节点无需统计，无需排序，无需输出。
2. 链表可能为空。（头节点地址为 ?1）。

思路

1. 先将所有结点用一个哈希表存起来，key 是结点的地址，value 是结点的三个信息，用结构体存储。
2. 根据给定的头结点，将链表中的结点放到另一个容器当中。
3. 对容器中的结点进行排序，然后输出。注意，最后一个结点的 next 要输出 -1 。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

struct Node {
    string address;
    int key;
    string next;
    //设定排序规则
    bool operator <(const Node& x)const
    {
        return key < x.key;
    }
};

int main()
{
    int n;
    string head;
    cin >> n >> head;

    //输入结点信息
    unordered_map<string, Node> num;
    for (int i = 0; i < n; i++)
    {
        char address[10], next[10];
        int key;
        scanf("%s %d %s", address, &key, next);
        num[address] = { address,key,next };
    }

    //将存在链表中的筛选出来
    vector<Node> res;
    for (string i = head; i != "-1"; i = num[i].next)    res.push_back(num[i]);

    cout << res.size();
    if (res.empty()) puts(" -1");
    else
    {
        sort(res.begin(), res.end());	//对链表中结点的key值从小到大进行排序
        cout << " " << res[0].address << endl;
        for (int i = 0; i < res.size(); i++)
        {
            if (i + 1 == res.size())	//如果没有遍历到最后一个结点
                printf("%s %d -1\n", res[i].address.c_str(), res[i].key);
            else	//如果遍历到最后一个结点
                printf("%s %d %s\n", res[i].address.c_str(), res[i].key, res[i + 1].address.c_str());
        }
    }

    return 0;
}