两个有序链表的合并_将两个有序链表合并成一个有序链表

两个有序链表的合并为一个有序链表

例如：第一个存放的是 1，3,   5,   7,   9；第二个链表存放的是2,4,6,8,10

两个链表合并成一个链表，可以新创一个头结点把这两个链表的数据依次放在这个头结点的后面，

这时候有序就成了这个问题的关键。

可以定义两个指针指向这两个链表，并把这两个指针指向的数据进行比较，小的那个结点放在第三个链表后面，并把这个指针向后移动 ，直到最后，但是我们还要想到一个问题，最后的结点是谁的尾结点，谁的指针先指到空，第三个链表的尾结点就是相反的的链表的尾结点，意思是p指向链表1，q指向链表2，如果最后p是空，则链表3的尾结点就是链表2的尾结点。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
typedef int DataType;    //定义数据类型
typedef struct node       //用结构体定义结点类型
{
	DataType data;
	struct node *next;
}Linkstack;
 
typedef struct stack //定义包含两个结构体头指针的结构体
{
	Linkstack *one;
	Linkstack *two;
}Link;
 
//建立头结点
Linkstack *creat_linkstack()
{
	Linkstack *head = (Linkstack *)malloc(sizeof(Linkstack)); //在堆区申请空间
	if(NULL == head)
	{
		printf("malloc is fail\n");
		return NULL;
	}
	memset(head,0,sizeof(Linkstack));//清零
	head->next = NULL;//指向NULL
	return head;
}
 
//建立两个空链表的头指针并返回
Link *creat_empty_linkstack()
{
	Link *ls = (que *)malloc(sizeof(que));
	if(NULL == ls)
	{
		printf("ls malloc is fail\n");
		return NULL;
	}
	ls->one = creat_linkstack(sizeof(Linkstack)); //创建第一个链表的头指针
	ls->one->data = 1;
	ls->two = creat_linkstack(sizeof(Linkstack)); //创建第二个链表的头指针
	ls->two->data = 2;
	return ls;
} 
//建立两个完整的链表
int creat_per_linkstack(Link *ls)
{
	int i;
	Linkstack *p;
	Linkstack *r;
	p = ls->one;
	for(i = 3;i <= 9;i += 2)
	{
		r = (Linkstack *)malloc(sizeof(Linkstack));
		if(r == NULL)
		{
			printf("新建链表失败\n");
			return 0;
		}
		r->data = i;
		r->next = p->next;
		p->next = r;
		p = r;
	}
	p = ls->two;
	for(i = 4;i <= 10;i += 2 )
	{
		r = (Linkstack *)malloc(sizeof(Linkstack));
		if(r == NULL)
		{
			printf("新建链表失败\n");
			return 0;
		}
		r->data = i;
		r->next = p->next;
		p->next = r;
		p = r;
	}
	return 1;	
}
//合并两个链表
void task(Link *ls)
{
	Linkstack *p = ls->one;    //定义指针p指向第一个链表的头结点
	Linkstack *q = ls->two;    //定义指针q指向第一个链表的头结点
	Linkstack *head = (Linkstack *)malloc(sizeof(Linkstack));//创建一个头结点当合并后链表的        
                                                             //头结点
	Linkstack *pre = head;     //定义指针pre指向合并后的链表的头结点  
	while(p != NULL && q != NULL) //p和q有一个指向NULL则退出循环
	{
		if(p->data <= q->data) //当第一个链表结点数据小于第二个链表的结点数据
		{
			pre->next = p;     //合并后链表指向第一个链表结点
			p = p->next;       //然后使p的指针向后移动
		}
		else
		{
			pre->next = q;     //与p同理
			q = q->next;       //向后移动q的指针
		}
		pre = pre->next;
	}
	pre->next = p == NULL ? q : p; //如果p先指向NULL,则q还没遍历完，让pre直接指向剩下的q
	Linkstack *s = head->next; //头结点没有数据
	for(;s->next != NULL;s = s->next)
	{
		printf("%d ",s->data); //打印合并后的链表
	}
	printf("%d\n",s->data);
	return ;
}
int main()
{
	Link *ls = creat_empty_linkstack();
	creat_per_linkstack(ls);
	task(ls);
	return 0;
}