PAT A1052 Linked List Sorting

我的解法

解题思路：我的思路比较简单，可以完全看做一个排序题目，只需要最后将next重新设置一下即可。我的解法得了21分。

注意：PAT是真的恶心！！！题目绝对没透露包含无效节点，就是节点不在链表中，真的是恶心！！！那最后输出的时候到底要不要输出也没说清楚，什么鬼哦！！

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100010;
struct Node{
	int addr;
	int key;
	int next;
}node[maxn];

bool cmp(Node a,Node b){
	return a.key<b.key;
}

int main(){
	int n,h,addr,key,next;
	scanf("%d %d",&n,&h);
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&addr,&key,&next);
		node[i].addr=addr;
		node[i].key=key;
		node[i].next=next;
	}
//	printf("\n");
	sort(node,node+n,cmp);
	printf("%d %05d\n",n,node[0].addr);
	for(int i=0;i<n;i++){
		if(i==n-1) {
			node[i].next=-1;
			printf("%05d %d %d\n",node[i].addr,node[i].key,node[i].next);
		}
		else {
			node[i].next=node[i+1].addr;
			printf("%05d %d %05d\n",node[i].addr,node[i].key,node[i].next);		
		}
	}
		
	return 0;
}

算法笔记解法

解题思路：必须使用静态链表，找出有效节点！然后sort排序，给结构体加一个标志位，遍历链表，确定有效节点，前提要对每个节点的标志位初始化！！

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100010;
struct Node{
	int addr;
	int key;
	int next;
	int flag;
}node[maxn];

bool cmp(Node a,Node b){
	if(a.flag==-1||b.flag==-1){
		return a.flag>b.flag;
	}else{
		return a.key<b.key;
	}
}

int main(){
	int n,h,addr,key,next;
	scanf("%d %d",&n,&h);
	for(int i=0;i<maxn;i++) node[i].flag=-1;
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&addr,&key,&next);
		node[addr].addr=addr;
		node[addr].key=key;
		node[addr].next=next;
	}
	int p,k=0;
	//遍历静态链表，找出有效节点 
	for(p=h;p!=-1;p=node[p].next){
		node[p].flag=1;
		k++;
	}

	sort(node,node+maxn,cmp);
	
	if(k==0) printf("0 -1\n");
	else printf("%d %05d\n",k,node[0].addr);
	for(int i=0;i<k;i++){
		if(i==k-1) {
			node[i].next=-1;
			printf("%05d %d %d\n",node[i].addr,node[i].key,node[i].next);
		}
		else {
			node[i].next=node[i+1].addr;
			printf("%05d %d %05d\n",node[i].addr,node[i].key,node[i].next);		
		}
	}
		
	return 0;
}