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

小灰灰 2021-06-22 15:39 449阅读 0赞

#include<iostream>
    using namespace std;
    
    typedef struct lnode
    { //定义结点类型
        int data;
        struct lnode *next;//递归定义
    } lnode,*LinkList;
    
    void CreateList(LinkList &L,int n)
    { //创建新链表
        L=new lnode;//生成一个头结点
        L->next=NULL;//结点L的next置空
        for(int i=0; i<n; i++)
        { 
            lnode *p;
            p=new lnode;//生成新结点
            cin>>p->data;//输入结点数据域
            p->next=L->next;
            L->next=p;
        }
    }
    
    void MegerList(LinkList &LA,LinkList &LB,LinkList &LC)
    { 
        lnode *pa,*pb,*pc;//定义三个结点
        pa=new lnode;pb=new lnode;pc=new lnode;
        pa=LA->next;//pa指向链表LA的第一个结点
        pb=LB->next;//指向链表LB的第一个结点
        LC=LA;
        pc=LC;//pc指向LC，也就是指向LA
        while(pa&&pb)
        { //如果pa小于等于pb，把pa赋给pc的next域，pc指向pa，pa指向pa的下一个元素
            if(pa->data<pb->data)
            { 
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
           if(pa->data>pb->data)
            { //如果pa大于pb，把pb赋给pc的next域，pc指向pb，pb指向pb的下一个元素
                pc->next=pb;
                pc=pb;
                pb=pb->next;
            }
            if(pa->data==pb->data)
            { 
                pc->next=pa;
                pc=pa;
                pa=pa->next;
                pb=pb->next;
            }
        }
        pc->next=pa?pa:pb;//将非空链表的剩余段插入到pc所指结点之后
        delete LB;//释放LB的头结点
    }
    
    void display(LinkList &L)
    { 
        lnode *p;
        p=new lnode;
        p=L->next;
        while(p)
        { 
            cout<<p->data;
            p=p->next;
        }
    }
    
    int main()
    { 
        LinkList LA,LB,LC;
        int m,n;
        cout<<"请输入LA的长度：";
        cin>>m;
        cout<<"请逆序递减输入LA的元素：";
        CreateList(LA,m);
        cout<<"请输入LB的长度：";
        cin>>n;
        cout<<"请逆序递减输入LB的元素：";
        CreateList(LB,n);
        MegerList(LA,LB,LC);
        cout<<"合并后的链表LC为：";
        display(LC);
        return 0;
    }