Home PAT 1133 Splitting A Linked List
Post
Cancel

PAT 1133 Splitting A Linked List

Link

关于链表这类题目感觉做过好多次了… 不知道以前写过相关题解没有, 不过这里就再提醒一下自己, 输入结束后要从 head 遍历一遍, 以免有的节点不在链表中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int head,n,k;
struct node{
    int addr,data,next,id;
    bool operator<(const node&x)const{
        if(data<0&&x.data>=0) return true;
        else if(data>=0&&x.data<0) return false;
        else if(data<0&&x.data<0) return id<x.id;
        else{
            if(data>=0&&data<=k){
                if(x.data>=0&&x.data<=k) return id<x.id;
                else return true;
            }else{
                if(x.data>=0&&x.data<=k)
                    return false;
                else return id<x.id;
            }
        }
    }
}linkList[100010];
vector<node>realList;
int main() {
    scanf("%d%d%d",&head,&n,&k);
    for(int i=1;i<=n;++i){
        int addr,data,next;
        scanf("%d%d%d",&addr,&data,&next);
        linkList[addr]={addr,data,next};
    }
    int p=head,cnt=0;
    while(p!=-1){
        linkList[p].id=++cnt;
        realList.push_back(linkList[p]);
        p=linkList[p].next;
    }
    sort(realList.begin(),realList.end());
    printf("%05d %d ",realList[0].addr,realList[0].data);
    for(int i=1;i<realList.size();++i)
        printf("%05d\n%05d %d ",realList[i].addr,realList[i].addr,realList[i].data);
    printf("-1\n");
    return 0;
}
This post is licensed under CC BY 4.0 by the author.