PAT 1075. 链表元素分类

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而[0, K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K为10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出：第1个结点的地址；结点总个数，即正整数N (<= 105)；以及正整数K (<=1000)。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为[-105, 105]区间内的整数；Next是下一结点的地址。题目保证给出的链表不为空。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例：

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

分析

不是每个节点都一定在链表上，必须捋一遍，即从他给的第一个节点地址开始往后滤，直至碰到-1；

代码如下

#include<iostream>
using namespace std;
struct node{
	int data=0;
	int next=0;
};
int main(){
     /*b[3]存储三小段的头，e[3]存储三小段的尾巴，
     tag记录是否是第一次遇到三小段的元素是小段的头*/ 
	int firstaddress,N,K,flag=0,b[3]={-1,-1,-1},e[3]={-1,-1,-1},tag[3]={-1,-1,-1},address,begin;
	node list[100000];
	cin>>firstaddress>>N>>K;
    for(int i=0;i<N;i++){
    	node nod;
    	scanf("%d %d %d",&address,&nod.data,&nod.next);
    	list[address]=nod;
	}
	address=firstaddress;
	while(address!=-1){ // 分别处理成三小段 
		if(list[address].data<0){
			if(tag[0]==-1) {
			b[0]=address; e[0]=address; tag[0]=1;	
			}else{
				list[e[0]].next=address;
				e[0]=address;
			}
		}
		else if(list[address].data<=K){
			if(tag[1]==-1){
			b[1]=address; e[1]=address; tag[1]=1;
			}else{
				list[e[1]].next=address;
				e[1]=address;
			}
		}
		else{
		if(tag[2]==-1){
			b[2]=address; e[2]=address; tag[2]=1;
			}else{
				list[e[2]].next=address;
				e[2]=address;
			}	
		}
		address=list[address].next;
	}
	int temp; // 在合成一段的过程中总是指向当前段的末尾 
    for(int i=0;i<3;i++){   // 合成一段 
    	if(b[i]!=-1){ // 表示这一小段不是空的话 
    	if(flag++==0){ // 第一次遇见非空段，则把该非空段的头最为全段的头begin 
    	begin=b[i]; temp=e[i];	
		}
    	else{ // 不是第一次遇见非空段的话，直接接到temp 
    	list[temp].next=b[i];
		temp=e[i];	
		}	
	    }	
	}
	list[temp].next=-1; // 将结尾变成-1 
	while(begin!=-1){ // 输出最终结果 
    if(list[begin].next!=-1)
	printf("%05d %d %05d
",begin,list[begin].data,list[begin].next);
	else
	printf("%05d %d %d
",begin,list[begin].data,list[begin].next);
	begin=list[begin].next;	
	}
	return 0;
}