2.（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来的两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据_c语言有序单链表合并

代码实现的思路：

因为要将两个有序单链表合并为一个递增的有序单链表，所以我们建立了三个单链表La，Lb，Lc，但是要求结果链表仍然使用原来两个链表的存储空间，所以我们用La的头结点作为Lc的头结点，这样直接操作单链表后，输出La单链表和Lc单链表结果是一样的。然后我们算法实现的思路是用三个工作结点pa，pb，pc指向此结点，然后进行比较，pa指向的此结点依次与pb的结点比较，直到比此时pb结点小，然后pa向下一个结点进行移动，然后重复刚刚的比较，直到其中一个单链表已经到尾结点。因为是递增的有序链表，所以直接将其中一个还未比完的单链表剩下的结点接在Lc单链表后。

优化改进的地方：

此代码只能对两个递增的有序链表进行合并，本文采用的是尾插法，如果想实现从大到小递减的排序，可以使用头插法，修改CreateList即可。如果还想实现无序链表合并为有序链表，可以单独再加一个排序函数，比如void Bubble Sort（）{}，采用一个冒泡排序对单链表进行排序，将无序的单链表排好序后再进行合并。

欢迎大家理性讨论，刚写文，代码或者说明有问题请多担待，欢迎大家指出我的问题，如有不懂也可以询问我。代码和运行结果赋下：

#include<stdio.h>
#include<stdlib.h>
 
//定义单链表结点类型
typedef struct LNode
{
    int date;       
    struct LNode *next;     //指针指向下一结点
}LNode,*Linklist;
 
//初始化链表
int InitList(Linklist &L)           //这里使用的C++的地址引用，对L进行直接操作.c文件文件可能会报错，建议改成.cpp
{
    L =(Linklist)malloc(sizeof(Linklist));
    if (L==NULL)
    return 1;           //内存不足，分配失败
    L->next=NULL;   
    return 0;           //分配空间成功
}
 
//尾插法建立单链表（带头结点）
int CreateList(Linklist &L,int n)
{
    Linklist r;//创建尾指针
    r=L;       //让尾指针指向头结点
    int x;     //定义了一个x用于接收用户输入的int型数据
    for (int i = 1; i <= n; i++)
    {
        LNode *p=(LNode*)malloc(sizeof(Linklist));
        printf("请输入第%d个数字\n",i);
        scanf("%d",&x);     //将用户输入的数据接收到x中
        p->date=x;          //将x的数据赋给单链表的此结点的数据区中
        p->next=NULL;       //尾结点指针置空
        r->next=p;
        r=p;                //r指向新的表尾结点
    } 
}
 
//合并两个链表，用Lc头指针指向新表
int MergeList(Linklist &La,Linklist &Lb,Linklist &Lc)
{
    Linklist pa,pb,pc,m;
    //pa，pb，pc分别为链表La，Lb，Lc的工作指针，m为特殊情况下中间过渡用的指针
    pa=La->next;    //pa指向La单链表后面的next指向的结点
    pb=Lb->next;    //pb指向Lb单链表后面的next指向的结点
    Lc=pc=La;       //用La的头结点作为Lc的头结点
    while (pa && pb)        //相当于遍历pa和pb，直到其中有一个单链表的尾结点结束
    {
        if(pa->date > pb->date)     //La单链表当前pa指向的结点>Lb单链表当前pb指向的结点
        {
            pc->next =pb;           //pc的当前结点的next指向pb（比较下小的那一个，因为LC单链表是从小打大递增的）
            pc=pb;                  //pc指向当前的pb结点（相当于pc移动到了此时的pb结点）
            pb=pb->next;            //pb指向pb的下一个结点
        }
        else if(pa->date < pb->date)//La单链表当前pa指向的结点<Lb单链表当前pb指向的结点
        {
            pc->next=pa;            //pc的当前结点的next指向pa
            pc=pa;                  //pc指向当前的pa结点（相当于pc移动到了此时的pa结点）
            pa=pa->next;            //pa指向pa的下一个结点
        }
        else if(pa->date = pb->date)//La单链表当前pa指向的结点=Lb单链表当前pb指向的结点
        {   //此处采用了一个策略，当pa和pb的数据一样大时，我们摘取pa的数据，而将pb此结点释放点（因为要释放，所以要使用一个中间过渡的指针m去记录此时pb的结点，否则会造成后面的结点丢失）
            pc->next=pa;
            pc=pa;                  //pc指向当前的pb结点（相当于pc移动到了此时的pa结点）
            pa=pa->next;            //pa指向pa的下一个结点
            m=pb->next;             //用m去记录pb的next指向的结点，防止后续结点丢失
            free(pb);
            pb=m;                   //将记录的结点重新赋给pb
        }                
    }
    pc->next= pa?pa:pb;     //三目运算，未遍历结束的链表直接接在Lc链表后
    free(Lb);               //释放单链表Lb
}
 
//输出单链表的函数
void output(Linklist L)     //此处只需要输出单链表就行，不需要使用&对单链表直接操作
{
    Linklist p=L;
    p=L->next;
    while(p)                //用工作指针p依次遍历此单链表
    {
        printf("%3d",p->date);  //以3格的宽度输出整型数，不足3格时，左补空格
        p=p->next;
    }
}
 
int main()
{
    int n1,n2;              //定义两个int整型用以接收链表的个数
    Linklist La,Lb,Lc;      //创建三个单链表
    InitList(La);           //初始化
    InitList(Lb);
    printf("请输入第一个链表的个数\n");
    scanf("%d",&n1);
    CreateList(La,n1);      //建立单链表La
    printf("请输入第二个链表的个数\n");
    scanf("%d",&n2);
    CreateList(Lb,n2);      //建立单链表Lb
    MergeList(La,Lb,Lc);    //合并单链表La，Lb到Lc
    output(Lc);             //此处输出Lc和La都可以，因为上面是用La的头结点当做Lc的头结点
}

 运行结果：