/* ————————————————————————————————*/
// 将两个有序链表升序合并到第三个链表//
/* ——————————————————————————————*/

#include <stdio.h>
#include <stdlib.h>

/* 定义结构体 */
typedef struct Node
{
	int data;			 //数据域
	struct Node * pNext; //指针域
}NODE, * PNODE; 
//由于使用了typedef, 所以NODE <=> struct Node  ,  PNODE <=> struct Node * 


/* 函数声明 */
PNODE create_list();									 //创建一个链表
void merge_list(PNODE pHead, PNODE qHead, PNODE rHead);  //将两个链表，升序合并到另一个链表 
void traverse_list(PNODE pHead);						 //遍历整个链表并输出

int main()
{
	//三个链表，三个头指针 
	PNODE pHead = NULL;  //头指针为空，用来保存头结点的地址
	PNODE qHead = NULL;
	PNODE rHead = NULL;
/*————————————————————————————————————————————*/
	//初始化第三个链表【只需要分配一个不存放数据的头结点】 
	//初始化这一步也可以用一个函数来实现 

	PNODE r = (PNODE)malloc(sizeof(NODE));
	if(NULL == r)
	{
		printf("分配失败，程序终止！");
		exit(-1);
	}
	rHead = r;
	r->pNext = NULL;
/*————————————————————————————————————————————*/	
	pHead = create_list(); //创建一个链表，并返回头结点的地址给pHead
	qHead = create_list(); //创建一个链表，并返回头结点的地址给qHead
	
	printf("\n初始化");
	traverse_list(rHead);  //遍历整个链表
	
	merge_list(pHead, qHead, rHead); 
	
	printf("升序合并后");
	traverse_list(rHead);  //遍历整个链表

	return 0;
}

/* 调用函数 */
/*———————————————————————————————————————————————————————*/
PNODE create_list()
{
	int len;      //用来存放有效节点的个数
	int i;
	int temp_val; //临时存放用户输入结点数据域的值

	//分配一个不存放有效数据的头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));

	if(NULL == pHead)
	{
		printf("分配失败，程序终止！");
		exit(-1);
	}

	PNODE pTemp = pHead; //临时存放头结点的地址
	pTemp->pNext = NULL;

	printf("请输入您要生成的链表节点的个数： len = ");
	scanf("%d", &len);

	for(i = 0; i<len; i++)
	{
		printf("请输入第%d个节点数据域的值 ：", i+1);
		scanf("%d", &temp_val);
		
		//循环一次分配一个存放有效数据的结点
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL ==pNew)
		{
			printf("分配失败，程序终止！");
			exit(-1);
		}

		pNew->data = temp_val;
		
		//尾插法 
		pTemp->pNext = pNew;
		pNew->pNext = NULL;  //每分配一个结点,这个结点就是最后一个,所以它的指针域（pNext）为空
		pTemp = pNew;        //保证前一个结点的指针域都指向后一个结点
	}

	return pHead;  //返回头结点的地址

}
/*———————————————————————————————————————————————————————*/
void merge_list(PNODE pHead, PNODE qHead, PNODE rHead)
{
	PNODE p, q, r;
	
	p = pHead->pNext;  //p指向第一个有效结点 
	q = qHead->pNext;  //q指向第一个有效结点 

	r = rHead;      //r指向rHead所指向的头结点【第三个链表的头结点】 
	while(NULL != p && NULL != q)
	{		 
    	//将两个结点的数据进行比较，数据较小的结点接在头结点后面，
		if(p->data <= q->data)
		{
			r->pNext = p;
			p = p->pNext;
		}
		else
		{
			r->pNext = q;
			q = q->pNext;
		}
		r = r->pNext;  //【重要的一步】移动第三个链表的指针 
	}
	//若其中一个链表的结点已经全接在新表中则将另一个链表的剩余结点接在新表的后面
	r->pNext = (NULL != p) ? p : q;
//	free(qHead);
//	free(pHead);

	return;
}

/*———————————————————————————————————————————————————————*/
void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;  //头结点的指针域赋给r,即首结点赋给r 【注意区分头结点和首结点】

	printf("链表的数据为：\n");
	while(NULL != p)
	{
		printf("%d ", p->data);
		p = p->pNext;        //下一个结点赋给r
	}

	printf("\n\n");

	return;
}