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

[题目分析]

合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。

#include<stdio.h>
#include<stdlib.h>
//定义存储结构
typedef struct {
    int date;//这里为图方便，只以int数据类型为例子
}Date;

typedef struct LNode {
    Date elem;
    struct LNode *next;
}Lnode ,*Linklist;

//单链表初始化
int InitList(Linklist &L)//&L可以直接对L操作，用到的是c++的部分知识，这样不用返回结构体
{
    L=(Linklist)malloc(sizeof(LNode));//c语言开辟空间
    //L=new Lnode;c++语言开辟空间
    L->next=NULL;//头节点指针域置为空
    return 1;//初始化完毕
}
//后插法创建单链表
void CreateList(Linklist &L,int n)//同样也用到了c++引用的知识
{   //n为用户要输入的个数
    Linklist r;//创建尾指针
    r=L;//指向头节点
    for(int i=0;i<n;i++)
    {
        Linklist p=new LNode;//开辟空间，p为节点
        printf("请输入第%d个数字\n",i+1);
        scanf("%d",&p->elem.date);//别忘取&
        //
        p->next=NULL;
        r->next=p;//将新节点插入r之后
        r=p;//r指向新的尾节点
    }
    
}
void MergeList(Linklist &La,Linklist &Lb,Linklist &Lc)
{//合并链表La和Lb，合并后的新表使用头指针Lc指向
    Linklist pa=La->next;  Linklist pb=Lb->next;
   //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
    Linklist pc;
   Lc=pc=La;  //用La的头结点作为Lc的头结点
   while(pa && pb)//到任意一个链表的尾节点结束
   { if(pa->elem.date<pb->elem.date)
   { pc->next=pa;pc=pa;pa=pa->next;}
     //取较小者La中的元素，将pa链接在pc的后面，pa指针后移
   else if(pa->elem.date>pb->elem.date) {pc->next=pb; pc=pb; pb=pb->next;}
      //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
     else //相等时取La中的元素，删除Lb中的元素
   {pc->next=pa;pc=pa;pa=pa->next;
     Linklist q=pb->next;delete pb ;pb =q;//free(pb);也可以
   }
     }
 pc->next=pa?pa:pb;    //插入剩余段
     delete Lb;            //释放Lb的头结点
}
//输出数据
void output(Linklist L)
{
    Linklist p=L;
    p=L->next;
    while(p)
    {
        printf("%2d",p->elem.date);
        p=p->next;
    }
}
int main()
{
    //创建2个链表
    Linklist La,Lb,Lc;
    //初始化
    InitList(La);
    InitList(Lb);
    //输入数据
    int n1,n2;
    printf("请输入每条链表的个数\n");
    scanf("%d %d",&n1,&n2);
    printf("请输入第1个链表的数据\n");
    CreateList(La, n1);
    printf("请输入第2个链表的数据\n");
    CreateList(Lb, n2);
    //调用此函数
    MergeList(La,Lb,Lc);
    output(Lc);
}

运行结果