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

/*将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它其它的存储空间。表中不允许有重复数据 */

typedef struct node
{
	int date;
	struct node *next;
}Linklist;
//构造头节点
Linklist* toujiedian(Linklist *L)
{ 
	L=(Linklist*)malloc(sizeof(Linklist));
	L->next=NULL;
	return L;

 } 
 Linklist* chushihualianbiao (int e)
 {
 	int d=1,r;
 	Linklist *L=toujiedian(L),*a,*b;
 	a=L;
 	int i;
 	for(i=0;i<e;i++,d++)
 	{
 		b=(Linklist*)malloc(sizeof(Linklist));
 		
 		printf("输入第%d个数",d);
 		scanf("%d",&r);
 		b->date=r;
 		b->next=NULL;
 		a->next=b;//这里别接错线 
 		a=a->next;

	 }
	 
 	return L;
 }

 void spelling(Linklist *L)
 {
 	Linklist *a;
 	a=L->next;
printf("你输入的链表为：\n");
 	while(a)
	 {
 		printf("%d\t",a->date);
 		a=a->next;
	 }
 }


Linklist* MergeList(Linklist *La,Linklist *Lb)
 
	{//合并链表La和Lb，合并后的新表使用头指针Lc指向
	Linklist *Lc;
    Linklist *pa,*pb,*pc,*q;
	  pa=La->next; pb=Lb->next;   
 
	  //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
 
	  Lc=pc=La; //用La的头结点作为Lc的头结点
 
	  while(pa && pb)
 
	{if(pa->date<pb->date){pc->next=pa;pc=pa;pa=pa->next;}
 
	    //取较小者La中的元素，将pa链接在pc的后面，pa指针后移
 
	    else if(pa->date>pb->date) {pc->next=pb; pc=pb; pb=pb->next;}
 
	     //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
 
	    else //相等时取La中的元素，删除Lb中的元素
 
	    {     pc->next=pa;pc=pa;pa=pa->next;
 
	          q=pb->next;free (pb) ;pb =q;
 
	    }
 
	 }
 
	 pc->next=pa?pa:pb;   //插入剩余段
 
	    free (Lb);           //释放Lb的头结点
    return Lc;
	} 


int main() 
{
	   Linklist *L;
	   int e; 
    toujiedian(L);
    printf("输入第一个递增链表长度");
   	scanf("%d",&e) ;
    L=chushihualianbiao (e);
    spelling(L);
    Linklist *P,*O;
    int k; 
    toujiedian(P);
    printf("\n输入第二个递增链表长度");
   	scanf("%d",&k) ;
    P=chushihualianbiao (k);
    spelling(P);
    printf("\n两个链表合成后为:\n");
    //O=lianbiaoronghe(L,P );
    O=MergeList(L,P);
    spelling(O);
	return 0;
}