PAT (Basic Level) Practice （中文）1075 链表元素分类 (25 分)_综合

PAT (Basic Level) Practice （中文）1075 链表元素分类 (25 分)

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [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

解题思路

题不难, 输出格式很恶心
使用unordered_map来记录一个address和对应的结点Node
按照负数,小于等于K和大于K分成三类, 这里没必要再用链表形式,直接用vector存下来
将三个vector的内容分别输出, 记得判断是不是空的vector
每行输出的是本Node的address, 还有val以及next

AC code

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;struct Node{
    int val;int next;int cur;
};
int main(){
    unordered_map<int,Node> mp;  //记录原始数据int head,tail,nodeNum,K;int add,data,next;cin >> head >> nodeNum >> K;for(int i=0;i<nodeNum;i++){
    cin >> add >> data >> next;auto p = new Node();p->val = data; p->next = next; p->cur=add;mp[add] = *p;}  vector<Node> neg,lessK,moreK;int neg_head=-1,lessK_head=-1,moreK_head=-1;tail = head;while(tail!=-1){
    if(mp[tail].val<0){
    neg.push_back(mp[tail]);if(neg_head==-1) neg_head=tail;}else if(mp[tail].val<=K){
    lessK.push_back(mp[tail]);if(lessK_head==-1) lessK_head=tail;}else{
    moreK.push_back(mp[tail]);if(moreK_head==-1) moreK_head=tail;}tail = mp[tail].next;}int cur;    if(neg_head!=-1){
    cur=neg_head;int i;for(i=0;i<neg.size()-1;i++){
    printf("%05d %d %05d\n",cur,neg[i].val,neg[i+1].cur);cur = neg[i+1].cur;}if(lessK_head==-1 and moreK_head==-1) printf("%05d %d %d\n",cur,neg[i].val,-1);else if(lessK_head==-1) printf("%05d %d %05d\n",cur,neg[i].val,moreK_head);else printf("%05d %d %05d\n",cur,neg[i].val,lessK_head);}    if(lessK_head!=-1){
    cur=lessK_head;int i;for(i=0;i<lessK.size()-1;i++){
    printf("%05d %d %05d\n",cur,lessK[i].val,lessK[i+1].cur);cur = lessK[i+1].cur;}if(moreK_head==-1) printf("%05d %d %d\n",cur,lessK[i].val,-1);else printf("%05d %d %05d\n",cur,lessK[i].val,moreK_head);}    if(moreK_head!=-1){
    cur=moreK_head;int i;for(i=0;i<moreK.size()-1;i++){
    printf("%05d %d %05d\n",cur,moreK[i].val,moreK[i+1].cur);cur = moreK[i+1].cur;}printf("%05d %d %d\n",cur,moreK[i].val,-1);}    return 0;    
}