PAT (Advanced Level) Practice 1052 Linked List Sorting

古城微笑少年丶 2023-06-24 15:23 31阅读 0赞

注意：给出的结点中，有的结点可能不再链表上，所以要遍历判断一下。

另外，所有的结点可能都不在链表上，这时候要输出“0 -1”

ps：“0 -1”这个有点流氓，当时做的时候知道会存在所有结点都无效的情况......但是就是不知道如何输出

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    #define max_size 100010
    struct Node{
        int index;
        int key;
        int next;
        int flag;
        Node(){
            flag = -1;
        }
    };
    bool cmp(struct Node n1,struct Node n2){
            return n1.key < n2.key;
    }
    int main()
    {
        int n,add;
        scanf("%d%d",&n,&add);
        struct Node node[max_size];
        struct Node result[max_size];
    
        for(int i=0;i<n;i++){
            int index;
            int key;
            int next;
            scanf("%d%d%d",&index,&key,&next);
            node[index].index = index;
            node[index].key = key;
            node[index].next = next;
            node[index].flag = 1;
        }
        int list_size = 0;
        if(node[add].flag != 1){
            printf("0 -1");
        }else{
            while(true){
            result[list_size++] = node[add];
            if(node[add].next == -1) break;
            add = node[add].next;
        }
    
        sort(result,result+list_size,cmp);//使用result数组，用存储空间换取速度
    
        printf("%d %05d\n",list_size,result[0].index);
        for(int i=0;i<list_size-1;i++){
            printf("%05d %d %05d\n",result[i].index,result[i].key,result[i+1].index);
        }
        printf("%05d %d -1\n",result[list_size-1].index,result[list_size-1].key);
        }
    
        return 0;
    }