【数据结构】链表的应用-两个有序单链表合并

例题2-7：请设计算法，将两个按值递增有序的单链表合并成一个按值递增有序的单链表

进行了：原地处理和异地处理

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#define LElemType int
using namespace std;
typedef struct LNode{
    LElemType data;
    struct LNode *next;
    LNode ( LElemType Data=0, struct LNode *Next=NULL){
        data=Data;
        next=Next;
    }
}LNode,*LinkList;
void InitLinkList(LinkList &L){
    L=new LNode ;
}
void CreateLinkList_Tail(LinkList &L, int n=0){  //尾插法
    L=new LNode ;
    LinkList pre=L,tmp;
    LElemType Data;
    for (int i=0;i<n;i++){
        printf("请输入第%d个元素的data : 
",i+1);
        cin>>Data;
        tmp=new LNode (Data);
        pre->next=tmp;
        pre=tmp;
    }
}
void CreateLinkList_Head(LinkList &L, int n=0){ //头插法
    L=new LNode;
    LinkList Tail,tmp;
    LElemType Data;
    for(int i=0;i<n;i++){
        printf("请输入第%d个元素的data : 
",i+1);
        cin>>Data;
        tmp=new LNode(Data);
        tmp->next=L->next;
        L->next=tmp;
    }
}
int ListIsEmpty(LinkList &L){
    if(L->next){
        return 1;
    }
    return 0;
}
int ListLength(LinkList &L){
    int Len=0;
    LinkList p=L->next;
    while(p){
        //printf("%d
",p->data);
        Len++;
        p=p->next;
    }
    return Len;
}
void OutputLinkList(LinkList &L){
    LinkList p=L->next;
    while(p){
        printf("%d%c",p->data,p->next==NULL?
: );
        p=p->next;
    }
}
void GetElem(LinkList L,int pos,LElemType &e){
    int i=1;
    LinkList p=L->next;
    while(p&&i<pos){
        i++;
        p=p->next;
    }
    if( i > pos || !p){
        printf(" "GetElem" pos is error
");
        return ;
    }
    e=p->data;
}
LElemType LocateElem(LinkList L,LElemType e){
    int j=1;
    LinkList p=L->next;
    while(p&&p->data!=e){
        j++;
        p=p->next;
    }
    if(!p){
        printf("" LocateElem " not exist E : %d 
",e);
        return 0;
    }
    return j;
}
void ListInsert(LinkList &L,int i,LElemType e){
    int j=0;
    LinkList p=L,s;
    while(p&&j<i-1){
        j++;
        p=p->next;
    }
    if(!p||j>i-1){
        printf("" ListInsert "index : %d error!
",i);
        return;
    }
    s=new LNode(e,p->next);
    p->next=s;
}
void ListDelete(LinkList &L, int i ,LElemType &e){
    int j=0;
    LinkList p=L,s;
    while(p->next&&j<i-1){
        j++;
        p=p->next;
    }
    if(!(p->next)||j>i-1){
        printf("" ListDelete " index: %d error!
",i);
        return ;
    }
    s=p->next;
    e=s->data;
    p->next=s->next;
    delete s;
}
void Array_List(LinkList &L,int a[],int n){
    InitLinkList(L);
    LinkList p,Pre=L;
    for(int i=0;i<n;i++){
        p=new LNode(a[i]);
        Pre->next=p;
        Pre=p;
    }
}
void ListMerge_Diff(LinkList La,LinkList Lb,LinkList &Lc){ //异地处理
    InitLinkList(Lc);
    LinkList Pre=Lc,pa=La->next,pb=Lb->next,p;
    while(pa&&pb){
        p=new LNode( pa->data<=pb->data?pa->data:pb->data,NULL);
        Pre->next=p;
        Pre=p;
        pa->data<=pb->data?pa=pa->next:pb=pb->next;
    }
    while(pa){
        p=new LNode(pa->data,NULL);
        Pre->next=p;
        Pre=p;
        pa=pa->next;
    }
    while(pb){
        p=new LNode(pb->data,NULL);
        Pre->next=p;
        Pre=p;
        pb=pb->next;
    }
}
void ListMerge(LinkList La,LinkList Lb,LinkList &Lc){ //原地处理
    LinkList Pre=La;
    Lc=Pre;
    LinkList pa=La->next;
    LinkList pb=Lb->next;
    while(pa&&pb){
        if(pa->data<=pb->data){
            Pre->next=pa;Pre=pa;pa=pa->next;
        }else{
            Pre->next=pb;Pre=pb;pb=pb->next;
        }
    }
    Pre->next=(pa!=NULL?pa:pb);
    delete Lb;
}
int main()
{
    int a[]={1,3,5,7};
    int b[]={2,4,6,8};
    LinkList La,Lb,Lc;
    Array_List(La,a,4);
    Array_List(Lb,b,4);
    puts("La:");OutputLinkList(La);
    puts("Lb:");OutputLinkList(Lb);
    ListMerge_Diff(La,Lb,Lc);
    puts("La+Lb:(Diff)");OutputLinkList(Lc);

    ListMerge(La,Lb,Lc);
    puts("La+Lb:");OutputLinkList(Lc);
    return 0;
}