#include <iostream>

using namespace std;

struct ListNode {

        int val;

         ListNode *next;

        ListNode(int x) : val(x), next(NULL) {}

    };

ListNode* createlist(int n)//有头节点的

{

    ListNode *head = (ListNode*)malloc(sizeof(ListNode));

    ListNode *pre = head;

    for (int i = ; i < n; i++)

    {

        ListNode *p = (ListNode*)malloc(sizeof(ListNode));

        cin >> p->val;

        pre->next = p;

        pre = p;

    }

    pre->next = nullptr;

    return head;

}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

    ListNode*temp;

    ListNode*t;

    if(l1== nullptr) return l2;

    if(l2== nullptr) return l1;

    if(l1->val>l2->val)//把头节点值小的放前面

    {

        t=l1;l1=l2;l2=t;

    }

    ListNode*head=l1;

    while(l2!= nullptr)

    {

        if(l1->next== nullptr)

        {

            l1->next=l2;

            return head;

        }

        else if(l1->val<=l2->val&&l1->next->val>=l2->val)

        {

            temp=l2->next;

            t=l1->next;

            l1->next=l2;

            l2->next=t;

            l1=l2;

            l2=temp;

        }

        else l1=l1->next;

    }

    return head;

}

int main() {

    ListNode* l1=createlist();

    ListNode* l2=createlist();

    ListNode *ans=mergeTwoLists(l1->next,l2->next);

    //ans=ans->next->next;

    while(ans!= nullptr)

    {

        cout<<ans->val<<endl;

        ans=ans->next;

    }

    return ;

}