## 题目

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:

 ``````1 `````` ``````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:

 ``````1 2 3 4 5 6 `````` ``````5 00001 11111 100 -1 00001 0 22222 33333 100000 11111 12345 -1 33333 22222 1000 12345 ``````

### Sample Output:

 ``````1 2 3 4 5 6 `````` ``````5 12345 12345 -1 00001 00001 0 11111 11111 100 22222 22222 1000 33333 33333 100000 -1 ``````

## 代码

 `````` 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 50 51 52 53 54 55 56 57 58 59 `````` ``````#include #include #include using namespace std; struct node{ int address; int key; int next; }nodes[100000],input[100000]; bool cmp(const node &a,const node &b) { return a.key < b.key; } int main() { int N,head; scanf("%d%d",&N,&head); for(int i=0;i

## 分析

1. algorithm的sort排序真好用，本来想建立静态链表后再手撸排序的，结果浪费了很多时间。