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

阳光穿透心脏的1/2处 2021-06-22 15:39 789阅读 0赞

#include<iostream>
    using namespace std;
    
    typedef struct lnode
    { 
        int data;
        struct lnode *next;
    }lnode,*LinkList;
    
    void CreateList(LinkList &L,int n)
    { 
        lnode *r,*p;
        L=new lnode;
        L->next=NULL;
        r=L;
        for(int i=0;i<n;i++){ 
            p=new lnode;
            cin>>p->data;
            p->next=NULL;
            r->next=p;
            r=p;
        }
    }
    
    void MegerList(LinkList &LA,LinkList &LB,LinkList &LC)
    { 
            lnode *pa,*pb,*pc,*p;
            pa=LA->next;
            pb=LB->next;
            pc=LC=LA;
            LC->next=NULL;
            while(pa||pb)
            { 
                if(!pa){ 
                    p=pb;
                    pb=pb->next;
                }
                else if(!pb){ 
                    p=pa;
                    pa=pa->next;
                }
                else if(pa->data<=pb->data)
                { 
                    p=pa;
                    pa=pa->next;
                }else{ 
                    p=pb;
                    pb=pb->next;
                }
                p->next=pc->next;
                pc->next=p;
            }
            delete 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;
    }