1052. Linked List Sorting (25)

1. 原题： https://www.patest.cn/contests/pat-a-PRactise/1052

2. 思路：

3. 源码（已AC）：

#include<iostream>#include<vector>#include<algorithm>//使用sort函数using namespace std;const int MAX = 100000;struct Node//结点结构体{	bool Operator<(const Node &b) const//重载比较运算符	{		return key < b.key;	}	Node() : add(0) {}//初始化地址为0	int add;//结点所在地址	int key;	int next;};int main(void){	//freopen("in.txt", "r", stdin);	int N, head;	cin >> N >> head;	vector<Node> nv(MAX);	for (int i = 0; i < N; i++)//存储数据	{		Node tem;		cin >> tem.add >> tem.key >> tem.next;		nv[tem.add] = tem;	}	if (nv[head].add == 0)//表示链表空	{		printf("0 -1/n");		return 0;	}	int pnext = head;	vector<Node> list;//保存有效结点的数组	while (pnext != -1)	{		list.push_back(nv[pnext]);		pnext = nv[pnext].next;	}	sort(list.begin(), list.end());//升序排序	int cnt = list.size();	printf("%d %05d/n", cnt, list[0].add);	for (int i = 0; i < cnt; i++)	{		if (i == cnt - 1)			printf("%05d %d -1/n", list[i].add, list[i].key);		else			printf("%05d %d %05d/n", list[i].add, list[i].key, list[i + 1].add);	}	return 0;}