PAT链表题综合（持续更新）
给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [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
#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;
} 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
#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;
} 可以比较上面两题的两个代码，提取相似之处作为以后遇到链表类问题的模板。 学习笔记，pat,牛客
以我的经历，我的带教有十几年工作经验，做过运维、后端开发、web测试，现在是高级软测，是行走的避坑指南