输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
思路一：迭代版本求解
1. 定义头指针head指向头指针指向首元节点,定义cur指向新的头结点；
2. 比较两个链表的大小，cur指向小的链表，小的链表指针后移；重复这个步骤，cur每次都是指向两个链表指针较小的那一个，直至某个链表遍历完指针指空；
3. cur直接接上不空的链表，返回首元节点head->next;
*/
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if (pHead1 == nullptr)
            return pHead2;
        if (pHead2 == nullptr)
            return pHead1;

        //创建头结点
        ListNode* head = new ListNode(-1);
        ListNode* cur = head;

        while (pHead1 && pHead2)
        {
            if (pHead1->val <= pHead2->val)
            {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }    
        if (pHead1)
            cur->next = pHead1;
        else
            cur->next = pHead2;
        return head->next;
    }

/*
思路二：递归方法。
创建一个新的节点，每次都是选取链表中头结点较小的节点作为新链表的后继节点。
*/
ListNode* Merge_2(ListNode* pHead1, ListNode* pHead2)
{
    if (pHead1 == nullptr && pHead2 == nullptr)
        return nullptr;
    if (pHead1 == nullptr)
        return pHead2;
    if (pHead2 == nullptr)
        return pHead1;
    ListNode * mergeHead = nullptr;
    if (pHead1->val <= pHead2->val)
    {
        mergeHead = pHead1;
        //重点在这，递归
        mergeHead->next = Merge(pHead1->next, pHead2);
    }
    else
    {
        mergeHead = pHead2;
        mergeHead->next = Merge(pHead1, pHead2->next);

    }
    return mergeHead;
}

/*
思路三：非递归方法。
判断特殊情况：若两个链表均为空则返回空；若其中一个链表为空则直接返回另一个非空链表。
两个非空有序链表合并：建立一个空节点，每次都选取p1,p2中比较小的那一个后继节点，直到p1,p2均遍历完成或其中一个链表遍历完成。
*/
ListNode* Merge_1(ListNode* pHead1, ListNode* pHead2)
{
    if (pHead1 == nullptr && pHead2 == nullptr)
        return nullptr;
    if (pHead1 == nullptr)
        return pHead2;
    if (pHead2 == nullptr)
        return pHead1;
    //mergeHead为合并后的链表的头结点，current为当前节点
    ListNode* p1 = pHead1, * p2 = pHead2, * mergeHead = nullptr, * current = nullptr;
    while (p1 != nullptr && p2 != nullptr)
    {   //若p1节点值<=p2节点值
        if (p1->val <= p2->val)
        {    //若一开始mergeHead为nullptr,需为mergeHead和current赋初值
            if (mergeHead == nullptr)
            {
                mergeHead = p1;
                current = mergeHead;
            }
            //在current后面插入一个p1节点
            else
            {
                current->next = p1;
                current = current->next;
            }
            p1 = p1->next;
        }
        else
        {
            if (mergeHead == nullptr)
            {
                mergeHead = p2;
                current = mergeHead;
            }
            else
            {
                current->next = p2;
                current = current->next;
            }
            p2 = p2->next;
        }
    }
    //遍历到最后若某一个链表已经遍历完成，则current直接接上另一个链表
    if (p1 == nullptr)
        current->next = p2;
    if (p2 == nullptr)
        current->next = p1;
    return mergeHead;
}