PAT-ADVANCED1052——Linked List Sorting

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464

题目描述：

题目翻译：

1052 链表排序

链表由一系列结构组成，这些结构在存储器中不一定相邻。 我们假设每个结构包含一个整数键值和一个指向下一个结构的Next指针。 现在给出一个链表，你需要按照键值的递增顺序对结构进行排序。

输入格式：

每个输入文件包含一个测试用例。 对于每个测试用例，第一行包含一个正整数N（< 10 ^ 5）和头节点的地址，其中N是存储器中节点的总数，节点的地址是5位正整数。 NULL由-1表示。

然后是N行，每行按以下格式描述一个节点：

Address Key Next

其中Address是内存中节点的地址，Key是[-10 ^ 5, 10 ^ 5]范围内的整数，Next是下一个节点的地址。题目保证所有节点的键值都是不同的，并且从头节点开始在链表中没有循环。

输出格式：

对每个测试用例，输出格式与输入格式相同，其中N是列表中节点的总数，所有节点必须按顺序排序。

输入样例：

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

输出样例：

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

知识点：链表

思路：首先根据首节点筛选出链表中的所有节点，再对筛选出的节点进行排序

根据题给的头节确定的链表中可能没有任何节点，测试点4就是这样一种情况。因此我们需要对一个flag数组来标记哪些位置的节点是存在的，哪些位置的节点是不存在的。对于头节点，如果其节点不存在，我们直接输出“0 -1”。

时间复杂度最差情况下是O(NlogN)。空间复杂度是O(100000)。

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct node {
	int address;
	int key;
	int next;
	node() {};
	node(int _address, int _key, int _next) : address(_address), key(_key), next(_next) {};
};

node Node[100000];
bool flag[100000];

bool cmp(node node1, node node2);

int main() {
	int N, first, now, key, next, cur;
	fill(flag, flag + 100000, false);
	scanf("%d %d", &N, &first);
	for(int i = 0; i < N; i++) {
		scanf("%d %d %d", &now, &key, &next);
		Node[now] = node(now, key, next);
		flag[now] = true;
	}
	vector<node> nodes;
	if(!flag[first]){
		printf("0 -1\n");
		return 0;
	}
	cur = first;
	while(cur != -1) {
		nodes.push_back(Node[cur]);
		cur = Node[cur].next;
	}
	sort(nodes.begin(), nodes.end(), cmp);
	printf("%d %05d\n", nodes.size(), nodes[0].address);
	for(int i = 0; i < nodes.size(); i++) {
		if(i != nodes.size() - 1) {
			printf("%05d %d %05d\n", nodes[i].address, nodes[i].key, nodes[i + 1].address);
		} else {
			printf("%05d %d -1\n", nodes[i].address, nodes[i].key);
		}
	}
	return 0;
}

bool cmp(node node1, node node2) {
	return node1.key < node2.key;
}

C++解题报告：