A27930. 链表元素分类给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。输入每个输入包含一个测试用例。每个测试用例第 1 行给出：第…
填空题
困难
知识点
题目描述
链表元素分类
给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [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 (≤ 105)；以及正整数K (≤ 103)。结点的地址是 5 位非负整数，NULL 地址用 -1 表示。 接下来有 N 行，每行格式为： Address Data Next 其中 `Address` 是结点地址；
`Data` 是该结点保存的数据，为 [-105, 105] 区间内的整数；`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参考答案
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct LinkNode{ //链表结点
string adress;
int data;
string next;
};
int main(){
string start;
int n,k;
cin>>start>>n>>k;
unordered_map<string,LinkNode> link;
LinkNode node;
for(int i=0;i<n;i++){ //输入链表，按adress为key值存储在哈希表中
cin>>node.adress>>node.data>>node.next;
link.insert({node.adress,node});
}
vector<LinkNode> ans;
//第一轮，从前往后找出所有<0的，插入到结果序列ans中
for(auto pair=link.find(start); pair!=link.end(); pair=link.find(pair->second.next) ){
if(pair->second.data<0)
ans.push_back(pair->second);
}
//第二轮，从前往后找出所有[0,k]之间的，插入到结果序列ans中
for(auto pair=link.find(start); pair!=link.end(); pair=link.find(pair->second.next) ){
if(pair->second.data<=k && pair->second.data>=0)
ans.push_back(pair->second);
}
//第三轮，从前往后找出所有>k的，插入到结果序列ans中
for(auto pair=link.find(start); pair!=link.end(); pair=link.find(pair->second.next) ){
if(pair->second.data>k)
ans.push_back(pair->second);
}
//更新所有结点的next值
for(int i=0;i<ans.size()-1;i++)
ans[i].next=ans[i+1].adress;
ans[ans.size()-1].next="-1";
//输出
for(int i=0;i<ans.size();i++)
cout<<ans[i].adress<<" "<<ans[i].data<<" "<<ans[i].next<<endl;
return 0;
}
上一题
下一题