【PAT乙级】链表元素分类

正文索引 [隐藏]

题目描述:

给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而 [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 (≤10​5​​);以及正整数K (≤10​3​​)。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。

接下来有 N 行,每行格式为:Address Data Next

其中 Address 是结点地址;Data 是该结点保存的数据,为 [−10​5​​,10​5​​] 区间内的整数;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

解题思路:

创建4个vector,先按照顺序把链表按照结点数据来分成三类:①结点数据为负数的链表(放入v1);②结点数据在[0,K]内的链表(放入v2);③除以上俩种情况外的其它链表(放入v3)。最后再把v1、v2、v3里的所有元素全部push_back()进v当中进行输出。

AC代码:

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

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

int main()
{
    int Head,N,K;    //头结点地址Head、结点总个数N
    cin >> Head >> N >> K;
    for(int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        node[temp].address = temp;
        cin >> node[temp].data >> node[temp].next;
    }
    vector<LinkNode> v1,v2,v3,v;  //v1用来存放负值元素、v2用来存放[0,K]内的元素、v3用来存放剩下的元素
    for(int i = Head; i != -1; i = node[i].next)
    {
        if(node[i].data < 0)    //若结点数据为负值
        {
            v1.push_back(node[i]);
        }
        else if(node[i].data <= K)   //若结点数据在[0,K]内
        {
            v2.push_back(node[i]);
        }
        else
        {
            v3.push_back(node[i]);
        }
    }
    for(auto it : v1)
    {
        v.push_back(it);
    }
    for(auto it : v2)
    {
        v.push_back(it);
    }
    for(auto it : v3)
    {
        v.push_back(it);
    }
    for(int i = 0; i < v.size(); i++)
    {
        if(i != v.size()-1)
        {
            printf("%05d %d %05d\n",v[i].address,v[i].data,v[i+1].address);
        }
        else
        {
            printf("%05d %d -1\n",v[i].address,v[i].data);
        }
    }
    return 0;
}