PAT1052 Linked List Sorting 最后一个样例不得分

女爷i 2023-07-18 12:35 7阅读 0赞

**思路：**  
构造好链表，然后按照键值从小到大排序，输出最后排好序的链表

**易错点：**  
1.sort函数排序右区间应大于当前实际区间,右区间是开区间  
例如我们要对node\[100\]中前50项排序

sort(node,node+49,cmp);
    //是错误的，该函数排序区间【0，49）

正确写法应是：

sort(node,node+50,cmp);
    //排序区间【0，50）

2.存在特判，在题目没说明链表不为空时，要注意链表不存在的情况，此时输出

> 0 -1

**代码：**

#include<algorithm>
    #include<cstdio>
    using namespace std;
    struct Node{ 
        int add,data,next;
    }node[100005];
    bool cmp(Node a,Node b)
    { 
        return a.data<b.data;
    }
    int main()
    { 
        int n,beginadd;
        scanf("%d %d",&n,&beginadd);
        Node result[n+5];
        int address;
        for(int i=0;i<n;i++)
        { 
            scanf("%d",&address);
            scanf("%d%d",&node[address].data,&node[address].next);
            node[address].add=address;
        }
        int p=beginadd,count=0;
        while(p!=-1)//链表连接
        { 
            result[count]=node[p];
            p=node[p].next;
            count++;
        }
        //空链表，特判
        if(count==0)
        { 
            printf("0 -1\n");
            return 0;
        }
        sort(result,result+count,cmp);
        printf("%d %05d\n",count,result[0].add);
        for(int i=0;i<count;i++)
        { 
            if(i!=count-1)printf("%05d %d %05d\n",result[i].add,result[i].data,result[i+1].add);
            else printf("%05d %d -1",result[i].add,result[i].data);
        }
        return 0;
    }