两个有序链表合并成一个有序的单链表

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

算法描述

（1）定义一个合并后的指针pc指向La表的头结点。由于要求不占用新的存储空间，所有用La的头结点当做新表的的头结点。
（2）依次从La和Lb表中取出最小的的元素，然后将其链接到新表后，直到其中一个表为空。
（3）最后，将La或Lb中剩余的元素链接到新表后即可。

算法分析

时间复杂度：O(La.length+Lb.length)
空间复杂度：O(0)

代码实现

/*合并两个链表*/
int MergeList_L(LinkList &La,LinkList &Lb) {
    LinkList pa = La->next;
    LinkList pb = Lb->next;
    LinkList pc = La;  //用使用La的头结点 作为合成后的头结点 
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next = pa;
            pc = pa;  //将pc指针指向新链表的最后一个结点 
            pa = pa->next;
        }else{
            pc->next = pb;
            pc = pb;  //将pc指针指向新链表的最后一个结点 
            pb = pb->next;
        }
    } 
    pc->next = pa?pa:pb;
    free(Lb);
    return 0;
}

完整代码

#include <stdio.h>
#include <stdlib.h>
//定义一个链表的结点（元素） 
typedef struct LNode{
    int data;//数据域
    struct LNode *next;//指向自己类型的指针域  
}LNode,*LinkList;//LinkList 为LNode类型的指针 

/*初始化操作*/ 
int InitList_L(LinkList &L) {
    L=(LinkList)malloc(sizeof(LNode));//生成一个LNode类型的 头 结点 
    L->next=NULL;
    return 0;
}

/*获取链表的长度 */
int GetListLength_L(LinkList L){
    LinkList p = L->next; 
    int j = 0;
    while(p){
        p = p->next;
        j++;
    }
    return j;
}

/*头插法创建链表*/
int CreateListHead_L(LinkList &L,int n){
    for(int i=n;i>0;i--){
        LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成新的结点 
        printf("请输入第 %d 个的元素：",n-i+1);
        scanf("%d",&newNode->data);//将输入的值赋给新创建结点的data域 
        newNode->next = L->next;//将新生成的结点指向头结点的下一个结点 
        L->next = newNode;//将头结点指向新生成的结点 
    }
    return 0;
} 

/*尾插法创建链表*/
int CreateListRear_L(LinkList &L,int n){
    LinkList r=L;//尾指针指向此链表
    for(int i=0;i<n;i++){
        LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成新的结点 
        printf("请输入第 %d 个的元素：",i+1);
        scanf("%d",&newNode->data);
        newNode->next = r->next;//将新生成的结点指向头结点的下一个结点 
        r->next = newNode;//将新生成的结点指向头结点的下一个结点 
        r = newNode;//将尾指针指向新生成的结点，新结点每次都插入到最后 
    }
    return 0;
} 
/*取值（获取链表指定位置的数据） */
int GetElem_L(LinkList L,int i){
    int j=0;
    LinkList p=L->next;
    while(p&&j<i-1){
        p = p->next;
        j++;
    }
    return p->data;
} 
/*打印链表中的元素*/
int PrintList_L(LinkList L) {
    LinkList p = L->next;
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return 0;
}
/*合并两个链表*/
int MergeList_L(LinkList &La,LinkList &Lb) {
    LinkList pa = La->next;
    LinkList pb = Lb->next;
    LinkList pc = La;  //用使用La的头结点 作为合成后的头结点 
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next = pa;
            pc = pa;  //将pc指针指向新链表的最后一个结点 
            pa = pa->next;
        }else{
            pc->next = pb;
            pc = pb;  //将pc指针指向新链表的最后一个结点 
            pb = pb->next;
        }
    } 
    pc->next = pa?pa:pb;
    free(Lb);
    return 0;
}
main(){
     LinkList La,Lb;
    //初始化
    int aInitStatus;//La初始化状态 
    int bInitStatus;//Lb初始化状态 
    int isEmpty;//是否为空 
    int headInsertStatus;//头插法插入状态 
    int rearInsertStatus;//删除状态 
    int listLength;//链表长度 
    int num;//插入元素的个数 

    aInitStatus = InitList_L(La);
    bInitStatus = InitList_L(Lb);
    if(bInitStatus==0&&aInitStatus==0){
        printf("初始化成功！copyright@www.it1997.com\n");
    } else{
        printf("初始化失败！\n");
    } 

    /*尾插法*/ 
    printf("【尾插法】\n");

    /*创建链表La*/ 
    printf("请输入创建链表La元素的个数："); 
    scanf("%d",&num);
    rearInsertStatus = CreateListRear_L(La,num);
    if(rearInsertStatus==0){
        printf("尾插法插入成功！copyright@www.it1997.com\n");
    } else{
        printf("尾插法插入失败！copyright@www.it1997.com\n");
    } 
    printf("======华丽分割线======\n"); 
   printf("链表La为："); 
   PrintList_L(La);

   /*创建链表Lb*/ 
   printf("请输入创建链表Lb元素的个数："); 
    scanf("%d",&num);
    rearInsertStatus = CreateListRear_L(Lb,num);
    if(rearInsertStatus==0){
        printf("尾插法插入成功！copyright@www.it1997.com\n");
    } else{
        printf("尾插法插入失败！copyright@www.it1997.com\n");
    } 
    printf("======华丽分割线======\n"); 
    printf("链表Lb为："); 
       PrintList_L(Lb);
       printf("======华丽分割线======\n"); 
       MergeList_L(La,Lb);

       printf("合并后链表为："); 
       PrintList_L(La);

}