#include<iostream>
using namespace std;
struct ListNode
{
    int val;
    ListNode* next;
};

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(pHead1 == NULL)return pHead2;
    if(pHead2 == NULL)return pHead1;
    struct ListNode* p1 = (pHead1->val <= pHead2->val ? pHead1 : pHead2);
    struct ListNode* p2 = (pHead1->val > pHead2->val ? pHead1 : pHead2);
    struct ListNode* p = p1; //p1是主链
    // temp存放中间指针，有可能在p1中有可能在p2中，最终每次指向p1链两个node之间和大node最近的那个点
    struct ListNode* temp =NULL;
    while((p1 != NULL)&&(p2 != NULL)){
        if(p1->val <= p2->val){
            temp = p1;
            p1 = p1->next;
        }
        else {
            temp->next = p2;
            temp = p2;
            p2 = p2->next;
            temp->next = p1;
        }

    }
    if(p1 == NULL){
        temp->next =p2;
        return p;
    }else return p;
}

int main(){
    ListNode* one = new ListNode;
    one->val = 1;
    ListNode* two = new ListNode;
    two->val = 3;
    ListNode* three = new ListNode;
    three->val = 4;
    ListNode* one2 = new ListNode;
    one2->val = 1;
    ListNode* two2 = new ListNode;
    two2->val = 2;
    ListNode* three2 = new ListNode;
    three2->val = 5;
    one->next = two;
    two->next = three;
    three->next = nullptr;
    one2->next = two2;
    two2->next = three2;
    three2->next = nullptr;
    ListNode* res = Merge(one, one2);
    ListNode* cur = res;
    cout << "init success" << endl;
    while(cur != nullptr){
        cout << cur->val << endl;
        cur = cur->next; 
    }
    return 0;
}