【入门级C语言】合并两个链表并排序输出

解题思路:    

        直接创建两个不带有哨兵结点的链表保存数据，连接后对结点进行冒泡排序，最后输出排序好的链表，思路非常直接。

注意事项:

        因为没有哨兵结点，我做的时候没有考虑到交换头结点时，首指针依然指向原来的头结点，而实际上若头结点与次结点交换了顺序，首指针会依然指向原来的头结点即现在的次结点，从而导致错误。下面是实现代码。

参考代码:

#include<stdio.h>
#include<stdlib.h>
struct link{                //结点结构体
	int num,mark;
	struct link *pre,*next;
};
int main(){
	int n,m,i,flag=1;
	scanf("%d%d",&n,&m);
	struct link *a,*b,*p,*q,*pp,*qn,*head;  		//head指针为连接a，b后的首指针
	a=(struct link*)malloc(sizeof(struct link));
	b=(struct link*)malloc(sizeof(struct link));
	
	a->pre=b->pre=NULL;             //初始化a,b的首指针的前序结点指针为NULL
	//我自己规定每条链表的头结点的前序指针和尾结点的后序指针皆为NULL
	/*创建a链表*/
 	p=a;
	for(i=0;i<n;i++){
		scanf("%d%d",&p->num,&p->mark);
		if(i<n-1){
			q=(struct link*)malloc(sizeof(struct link));
			p->next=q;
			q->pre=p;
			p=q;
		}
		else
			p->next=NULL;
	}
	/*创建b链表*/
	p=b;
	for(i=0;i<m;i++){
		scanf("%d%d",&p->num,&p->mark);
		if(i<m-1){
			q=(struct link*)malloc(sizeof(struct link));
			p->next=q;
			q->pre=p;
			p=q;
		}
		else
			p->next=NULL;
	}
	
	/*因为没有哨兵结点，所以需要判断a,b链表里有没有结点，
	因为创建链表时我先创建了一个无实际值的结点，
	如果n,m有一个为0，我就需要把那个0个结点的链表剔除掉，
	否则会将一个无实际值的结点纳入到连接后的链表中，
	从而产生错误
	下面是进行判断*/
	if(n!=0&&m!=0){
		head=p=a;
		while(p->next)
			p=p->next;
		p->next=b;
		b->pre=p;
	}
	else
		if(n==0&&m==0){
			free(a);        //不能忘记从堆区释放申请来的内存空间
			free(b);        //不能忘记从堆区释放申请来的内存空间
			return 0;
		}
		else
			if(n==0){
				free(a);        //不能忘记从堆区释放申请来的内存空间
				head=b;
			}
			else{
				free(b);        //不能忘记从堆区释放申请来的内存空间
				head=a;
			}
	/*使用冒泡排序法进行排序操作*/
	while(flag){
		flag=0;
		p=head;
		while(p->next){
			if(p->num>p->next->num){
				q=p->next;			//直接使用四个指针分别指向四个连续的结点
				pp=p->pre;          //等于是四个结点直接重新连一下
				qn=q->next;         //不然只使用一个俩个指针头容易晕
				if(pp)
					pp->next=q;
				else                //！！！如果头结点参与了交换，那么就要重新把head指针指向新的头结点
					head=q;
				q->pre=pp;
				if(qn)
					qn->pre=p;
				p->next=qn;
				q->next=p;
				p->pre=q;
				p=q;
				flag=1;
			}
			p=p->next;
		}
	}
	/*输出排序后链表并释放内存空间*/
	p=head;
	while(p){
		printf("%d %d\n",p->num,p->mark);
		q=p;
		p=p->next;
		free(q);
	}
}