【PAT甲级】Linked List Sorting

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/89452300

Problem Description：

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​5​​) 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​5​​,10​5​​], 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

解题思路：

创建一个结构体数组LinkList，其中包括当前结点的地址address、当前结点的数据data、下一个结点的地址next。按照链表结点的地址来将结点排序并依次放入vector中，用cnt来记录结点vector中的结点数量，当结点数为0时输出"0 -1"（这个测试点有1分），当结点数不为0时，根据结点数据data来对链表进行排序，然后无脑输出即可。

AC代码：

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

struct LinkList
{
    int address;    //当前结点的地址
    int data;       //当前结点的数据
    int next;       //下一结点的地址
}node[MAX];

bool cmp(LinkList a,LinkList b)   //根据结点数据升序排列
{
    return a.data < b.data;
}

int main()
{
    int Head,N;   //头结点Head,结点总个数N
    cin >> N >> Head;
    for(int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        node[temp].address = temp;
        cin >> node[temp].data >> node[temp].next; 
    }
    vector<LinkList> v;   //存放链表
    int cnt = 0;
    for(int i = Head; i != -1; i = node[i].next)  //先根据地址来将链表排序
    {
        v.push_back(node[i]);
        cnt++;
    }
    if(cnt == 0)   //当没有输入链表时
    {
        printf("0 -1\n");
    }
    else
    {
        sort(v.begin(),v.end(),cmp);   //根据链表的data升序排列
        printf("%d %05d\n",cnt,v[0].address);
        for(int i = 0; i < cnt; i++)
        {
            printf("%05d %d ",v[i].address,v[i].data);
            if(i != cnt-1)
            {
                printf("%05d\n", v[i+1].address);
            }
            else
            {
                printf("-1\n");
            }
        }
    }
    return 0;
}