1052 Linked List Sorting (25分)

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (<105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Key Next

where Address is the address of the node in memory, Key is an integer in [−105,105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

5 00001 11111 100 -1 00001 0 22222 33333 100000 11111 12345 -1 33333 22222 1000 12345

Sample Output:

5 12345 12345 -1 00001 00001 0 11111 11111 100 22222 22222 1000 33333 33333 100000 -1

题目大意：

输入：给你一个下面要展示的结点个数，和链表的头结点，让你根据结点的值从小对大对链表进行排序。输出：输出链表的结点个数和排序后的头结点，再按照输入的格式输出整个链表

解题思路：

这题思路还是明确的，就是用数组下标为结点地址保存结点的属性，然后通过sort函数进行排序，最后输出。但是有一个坑点，题目给的结点并不是全部在链表中的，需要你从头到尾遍历一遍，确认链表的结点是哪些。我们可以用flag=true标记是链表结点，然后为了排序的时候将非链表结点放到数组后面，可以使用return a.flag > b.flag;

代码：

#include<iostream> #include<algorithm> using namespace std; struct Node { int address, value, next; bool flag; }node[100000]; bool cmp(Node a, Node b) { if(!a.flag || !b.flag) return a.flag > b.flag; else return a.value < b.value; } int main() { int n, head, cnt = 0; scanf("%d %d", &n, &head); for(int i = 0; i < n; ++i) { int tadddress; scanf("%d", &tadddress); node[tadddress].address = tadddress; scanf("%d %d", &node[tadddress].value, &node[tadddress].next); } for(int index = head; index != -1; index = node[index].next) { node[index].flag = true; ++cnt; } if(cnt == 0) printf("0 -1\n"); else { sort(node, node + 100000, cmp); printf("%d d\n", cnt, node[0].address); for(int i = 0; i < cnt; ++i) { printf("d %d ", node[i].address, node[i].value); if(i != cnt - 1) printf("d\n", node[i+1].address); else printf("-1\n"); } } return 0; }