        ## PTA(Advanced Level)1052.Linked List Sorting.

2020-07-02

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:

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

``````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️⃣用静态链表存结点, 从头指针开始遍历并存入一个`vector`, 对`vector`进行排序, 再按照规定的格式输出即可.
语言 方法
7945 id1N8
O31W5
• 抖音美女「紫然」钟婷的闺蜜
• 9408 2007/07/27 22:02:15
• ⚠️要区分实际链表长度和给你的结点数, 两者不一定相等.
• ⚠️实际链表长度为0的时候, 输出`0 -1`
``````#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
struct node
{
int address;
int data;
int next;
int id;
}LinkList[MAXN];
bool cmp(node a, node b)
{
return a.data < b.data;
}
int main()
{
int n, st;
scanf("%d%d", &n, &st);
int address, next;
int data;
for(int i=0;i<n;i++)
{
scanf("%d %d %d", &address, &data, &next);
LinkList[address].address = address;
LinkList[address].data = data;
LinkList[address].next = next;
LinkList[address].id = i;
}	//静态链表
vector<node> v;
int cur = st;
while(cur != -1)
{
v.push_back(LinkList[cur]);
cur = LinkList[cur].next;
}
sort(v.begin(), v.end(), cmp);
if(v.size() == 0)
{
printf("0 -1\n");
return 0;
}
printf("%d %05d\n", v.size(), v.address);
for(int i=0;i<v.size();i++)
{
printf("%05d %d", v[i].address, v[i].data);
if(i == v.size()-1)
printf(" -1\n");
else
printf(" %05d\n", v[i+1].address);
}
return 0;
}``````

0条评论

×

¥.00

• 全站无广告

• 全屏阅读

• 全站电子书免费读

• VIP专属标识