单链表的合并（c++实现）

左手的ㄟ右手 2023-09-28 16:19 3阅读 0赞

## 场景： ##

`两个非递减单链表合并为一个非递减单链表`

例如：\{1,3,6,8\}和\{2,3,7,9,11,13\}合并为\{1,2,3,3,6,7,8,9,11,13\}

--------------------

## 代码： ##

`提示：需考虑当一个表满后，将另一个表的剩余结点直接移到新链表。`

#include <iostream>
    
    typedef struct LNode{
        int data;
        struct LNode *next;
    }LNode;
    
    void createLinkList(LNode *&head);
    void showLinkList(LNode *head);
    void mergeLinkList(LNode *head1, LNode *head2, LNode *&head3);
    using namespace std;
    
    int main(){
        LNode *h1,*h2,*h3;
        //连续创建三个表
        createLinkList(h1);
        createLinkList(h2);
        createLinkList(h3);
        //展示创建结果
        showLinkList(h1);
        showLinkList(h2);
        showLinkList(h3);
        //合并h1,h2到h3
        mergeLinkList(h1, h2, h3);
        //展示合并结果
        showLinkList(h3);
        return 0;
    }
    
    void createLinkList(LNode *&head){
        head = (LNode*)malloc(sizeof (LNode));
        head->next=nullptr;
        int data;
        LNode *p,*tail=head;
        cout << "**********尾插法**********（退出值：9999）" << endl;
        while(true){
            cout << "请输入结点的值：";
            cin >> data;
            if(data == 9999){
                break;
            }
            p = (LNode*)malloc(sizeof (LNode));
            tail->next = p;
            p->data = data;
            p->next = nullptr;
            tail = p;
        }
        cout << "结束成功！" << endl;
    }
    
    void showLinkList(LNode *head){
        cout << "【";
        int flag = 0;
        while(head->next!= nullptr){
            if(flag==0){
                head = head->next;
                cout << head->data;
                flag = 1;
            }
            if(head->next== nullptr){
                break;
            }
            head = head->next;
            cout << " " << head->data;
        }
        cout << "】" << endl;
        cout << "打印完毕！" << endl;
    }
    
    void mergeLinkList(LNode *head1, LNode *head2, LNode *&head3){
        if(head1->next== nullptr){
            head3 = head2;
            return;
        }
        if(head2->next== nullptr){
            head3 = head1;
            return;
        }
        head1 = head1->next;
        head2 = head2->next;
        LNode *tail = head3;
        while(true){
            if(head1->data>head2->data){
                do {
                    LNode *p;
                    p = (LNode*)malloc(sizeof (LNode));
                    tail->next = p;
                    p->next = nullptr;
                    p->data = head2->data;
                    head2 = head2->next;
                    tail = tail->next;
                    tail->next = nullptr;
                }while(head2!= nullptr && head1->data>head2->data);
                if(head2== nullptr){
                    while(head1!= nullptr){
                        LNode *p;
                        p = (LNode*)malloc(sizeof (LNode));
                        tail->next = p;
                        p->next = nullptr;
                        p->data = head1->data;
                        head1 = head1->next;
                        tail = tail->next;
                        tail->next = nullptr;
                    }
                    break;
                }
            }else{
                do {
                    LNode *p;
                    p = (LNode*)malloc(sizeof (LNode));
                    tail->next = p;
                    p->next = nullptr;
                    p->data = head1->data;
                    head1 = head1->next;
                    tail = tail->next;
                    tail->next = nullptr;
                }while(head1!= nullptr && head1->data<=head2->data);
                if(head1== nullptr){
                    while(head2!= nullptr){
                        LNode *p;
                        p = (LNode*)malloc(sizeof (LNode));
                        tail->next = p;
                        p->next = nullptr;
                        p->data = head2->data;
                        head2 = head2->next;
                        tail = tail->next;
                        tail->next = nullptr;
                    }
                    break;
                }
            }
        }
    }

--------------------

## 结果截图： ##

![716e817dc53d4100b967d5e0cb2c6c25.png][]

> 图1：插值建立两个新链表

![4280bcb66918477e8e1521bca3f11cd4.png][]

> 图2：新链表只建立，不插值

[716e817dc53d4100b967d5e0cb2c6c25.png]: https://img-blog.csdnimg.cn/716e817dc53d4100b967d5e0cb2c6c25.png
[4280bcb66918477e8e1521bca3f11cd4.png]: https://img-blog.csdnimg.cn/4280bcb66918477e8e1521bca3f11cd4.png