1.PAT乙级1075 链表元素分类 (25分)

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (≤)；以及正整数K (≤)。结点的地址是 5 位非负整数，NULL 地址用 − 表示。

接下来有 N 行，每行格式为： 

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 [ 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例： 

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例： 

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1
静态链表的应用，3种排序直接3个数组保存 
#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}list[100000];
vector<int> v[3];
int main() {
    int start, n, k, a;
    scanf("%d%d%d", &start, &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        scanf("%d%d", &list[a].data, &list[a].next);
    }
    int p = start;
    while(p != -1) {
        int data = list[p].data;
        if (data < 0)
            v[0].push_back(p);
        else if (data >= 0 && data <= k)
            v[1].push_back(p);
        else
            v[2].push_back(p);
        p = list[p].next;
    }
    int flag = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < v[i].size(); j++) {//flag控制打印
            if (flag == 0) {
                printf("%05d %d ", v[i][j], list[v[i][j]].data);
                flag = 1;
            } else {
                printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);
            }
        }
    }
    printf("-1");
    return 0;
}
2.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 (<) 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 −.

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 [−], 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
静态链表的应用，1种排序直接1个数组保存有效数据（输入中可能存在不是这个链表的节点），手写cmp函数 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct linke
{
	int adr,data, next;
}buf[100005];
bool cmp(linke& a, linke& b)
{
	if (a.data != b.data)
		return a.data < b.data;
}
int main()
{
	int n, begin,adr;
	while (scanf("%d%d", &n, &begin) != EOF)
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &adr);
			buf[adr].adr = adr;
			scanf("%d%d", &buf[adr].data, &buf[adr].next);
		}
		int p = begin;
		vector<linke>v;
		int ant = 0;
		while (p != -1)
		{
			ant++;
			v.push_back(buf[p]);
			p = buf[p].next;
		}
		if (ant == 0)
		{
			cout << "0 -1" << endl;
			continue;
		}
		sort(v.begin(), v.end(), cmp);
		printf("%d %05d\n", ant, v[0].adr);
		int flag = 0;
		for (vector<linke>::iterator it = v.begin(); it != v.end(); it++)
		{
			if (flag == 0)
            {
                printf("%05d %d ", (*it).adr, (*it).data);      
                flag=1;
            }
				
			else
				printf("%05d\n%05d %d ", (*it).adr, (*it).adr,(*it).data);
		}
		printf("-1\n");
	}
	return 0;
}
可以比较上面两题的两个代码，提取相似之处作为以后遇到链表类问题的模板。
另外两题的链接：