(PAT 1052) Linked List Sorting (链表)

红太狼 2022-03-25 08:09 152阅读 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 (<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

解题思路:

给出一串结点,有有效结点和无效结点(在链表上的是有效结点,链表外的为无效结点),筛选出有效结点,把他们根据key的大小排序后组成新的链表,最后输出链表

根据[https://blog.csdn.net/alex1997222/article/details/86553586][https_blog.csdn.net_alex1997222_article_details_86553586]中的模板解题即可,注意链表为空的情况

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 100010;
    struct Node {
    	int key;
    	int validation;
    	int Addr;
    	int next;  //指向下一个结点
    }nodes[MAXN];
    bool cmp(Node a, Node b) {
    	if (a.validation == -1 || b.validation == -1) {
    		return a.validation > b.validation;  //将有效结点左移
    	}
    	else {
    		return a.key < b.key;  //将数字从小到大排序
    	}
    }
    int main() {
    	int counter = 0;
    	int N, headAddr;
    	scanf("%d %d", &N, &headAddr);
    	for (int i = 0; i < MAXN; ++i) {
    		nodes[i].validation = -1;  //先全部设置为无效结点
    	}
    	for (int i = 0; i < N; ++i) {
    		int Addr, data, nextAddr;
    		scanf("%d %d %d", &Addr, &data, &nextAddr);
    		nodes[Addr].Addr = Addr;
    		nodes[Addr].key = data;
    		nodes[Addr].next = nextAddr;  //指向下一个结点
    	}
    	//遍历链表,挑选出有效结点
    	int p1 = headAddr;
    	while (p1 != -1) {
    		counter++;
    		nodes[p1].validation = 1;
    		p1 = nodes[p1].next;  
    	}
    	if(counter == 0){   //链表为空的情况要特别注意
    	  printf("%d %d",counter,-1);
    	  return 0;
    	}
    	sort(nodes, nodes + MAXN, cmp); //排序
    	for (int i = 0; i < MAXN; ++i) {
    		if (nodes[i + 1].validation == -1) {
    			nodes[i].next = -1;
    			break;
    		}
    		nodes[i].next = nodes[i + 1].Addr;
    	}
    	printf("%d %05d\n", counter, nodes[0].Addr);
    	for (int i = 0; i < MAXN; ++i) {
    		if(nodes[i].validation == -1) break;
    		if (nodes[i].next == -1) {
    			printf("%05d %d %d\n", nodes[i].Addr, nodes[i].key, nodes[i].next);
    		}
    		else {
    			printf("%05d %d %05d\n", nodes[i].Addr, nodes[i].key, nodes[i].next);
    		}
    	}
    	return 0;
    }

[https_blog.csdn.net_alex1997222_article_details_86553586]: https://blog.csdn.net/alex1997222/article/details/86553586