1133 Splitting A Linked List

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);
        }
    }
}
上一篇:165. 比较版本号


下一篇:Python全栈(第一部分)day2