#include <iostream>
using namespace std;
//定义链表结构
struct my_list{
    int val;
    my_list *next;
    my_list(int _val):val(_val),next(nullptr){}
};
my_list* merge(my_list* l1,my_list* l2)
{
    if(l1==nullptr) return l2;//实参为空 
    if(l2==nullptr) return l1;
    my_list head(0);//定义虚拟头节点
    my_list* node=&head;//操作节点
    while(l1!=nullptr && l2!=nullptr)
    {
        if(l1->val > l2->val)//node后面跟较小的节点 
        {
            node->next=l2;
            l2=l2->next;
        }
        else{
            
            node->next=l1;
            l1=l1->next;
        }
        node=node->next;//待比较节点后移 
        if(l1==nullptr){//l1为空，node后接l2 
            node->next=l2;
        }
        if(l2==nullptr)//l2为空，node后接l1 
        {
            node->next=l1;
        }
        
    } 
    return head.next;
};
int main(int argc, char *argv[])
{
    my_list *node0=new my_list(0);
    my_list *node1=new my_list(1);
    my_list *node2=new my_list(2);
    my_list *node3=new my_list(4);
    
    my_list *node4=new my_list(1);
    my_list *node5=new my_list(2);
    my_list *node6=new my_list(3);
    node0->next=node1;
    node1->next=node2;
    node2->next=node3;
    node3->next=nullptr;
    
    node4->next=node5;
    node5->next=node6;
    node6->next=nullptr;
    auto node=merge(node0,node4);
    while(node!=nullptr)
    {
        cout<<node->val<<" ";
        node=node->next;
    }
    
    return 0;
}