1133 Splitting A Linked List
题目大意
给一个链表和K,遍历链表后将<0的结点先输出,再将0~k区间的结点输出,最后输出>k的结点
核心思路
建立vector数组v1,v2,v3分别用来存储key值小于0的结点地址,key值大于0小于等于m的结点地址,key值大于m的结点地址。
按顺序遍历链表的每一个结点,取出key值在不同区间的结点地址,分别放入vector数组v1、v2、v3中。将vector数组v1,v2,v3中的结点的address按顺序放到vector数组v中。
按顺序输出每个结点的address,key和下一个结点的address
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=100005;
struct Node{
int address;
int key;
int next;
}node[maxn];
vector<int> v1;//存放key值小于0的结点地址
vector<int> v2;//存放key值大于0小于等于m的结点地址
vector<int> v3;//存放key值大于m的结点地址
vector<int> v;//整合v1,v2,v2到vector数组v中
int main(){
//读入初始结点的地址,结点总数,间隔
int begin,n,m;
cin>>begin>>n>>m;
//给每个结点赋值
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
node[a]={a,b,c};
}
//遍历链表,按顺序取出key值在不同区间的结点地址,分别放入vector数组v1、v2、v3中
for(int p=begin;p!=-1;p=node[p].next){
if(node[p].key<0) v1.push_back(p);
else if(node[p].key>=0&&node[p].key<=m) v2.push_back(p);
else v3.push_back(p);
}
//将v1,v2,v3中的address按顺序放到v中
for(int i=0;i<v1.size();i++) v.push_back(v1[i]);
for(int i=0;i<v2.size();i++) v.push_back(v2[i]);
for(int i=0;i<v3.size();i++) v.push_back(v3[i]);
//输出
for(int i=0;i<v.size();i++){
if(i!=v.size()-1){
printf("%05d %d %05d\n",node[v[i]].address,node[v[i]].key,node[v[i+1]].address);
}else{
printf("%05d %d -1\n",node[v[i]].address,node[v[i]].key);
}
}
}