Sword finger Offer learning summary - merging two sorted lists

This series is the learning summary of sword finger Offer, mainly the analysis and implementation of code cases:
Book links: http://product.dangdang.com/24242724.html
Original author's blog: http://zhedahht.blog.163.com/blog/static/254111742011101624433132/
The original author blog link has a complete project code download.

Merge two sorted linked lists

subject

Title: enter two ascending sorted linked lists, merge the two linked lists and make the nodes in the new linked list still rank in ascending order.
For example, input the linked list 1 and 2 in the diagram, and the combined linked list is shown in the linked list 3.

The definition of linked list node is as follows:

struct ListNode
{
    int       m_nKey;
    ListNode* m_pNext;
};

Solution at first sight:

When we consider merging two linked lists, if we can use a new virtual node.
We can define a new linked list, point to linked list 1 and linked list 2 with two pointers respectively, and compare the data size of nodes pointed to by them,
We select the small data of the two, insert it into the new list, and then move the new list pointer and the selected data pointer.

If it is necessary to merge on the existing chain list, we choose the one with the smaller value of two chain head nodes as the combined head node,
Then move back the head pointer of the selected linked list, and define a new pointer to the new linked list node currently built.

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    //Consider the case of empty list
    if (pHead1 == NULL)
        return pHead2;
    else if (pHead2 == NULL)
        return pHead1;

    ListNode* pMerged = NULL;
    ListNode* p = NULL;

    //Select which linked list has smaller header node data
    if (pHead1->m_nValue <= pHead2->m_nValue)
    {
        pMerged = pHead1;
        pHead1 = pHead1->m_pNext;
    }
    else
    {
        pMerged = pHead2;
        pHead2 = pHead2->m_pNext;
    }

    p = pMerged;//Pointer to the combined linked list

    while (pHead1!=NULL&&pHead2!=NULL)
    {
        if (pHead1->m_nValue <= pHead2->m_nValue)
        {
            p->m_pNext = pHead1;
            p = p->m_pNext;
            pHead1 = pHead1->m_pNext;

        }
        else
        {
            p->m_pNext = pHead2;
            p = p->m_pNext;
            pHead2 = pHead2->m_pNext;
        }
    }
    //Judgment of other conditions at the end of the cycle
    if (pHead1 == NULL&& pHead2!=NULL)
    {
        p->m_pNext = pHead2;
    }
    else if (pHead1 != NULL&& pHead2 == NULL)
    {
        p->m_pNext = pHead1;
    }
    return pMerged;
}

The realization of recursion

The above thinking, if we use the idea of recursion to understand, will appear more simple. The premise of recursion is divide and conquer.
We deal with the head node and the back node of the list respectively. Each recursion only deals with the head node and the remaining nodes of the list.

ListNode* Merge1(ListNode* pHead1, ListNode* pHead2)
{
    //Termination condition of recursion
    if (pHead1 == NULL)
        return pHead2;
    else if (pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;
    //Process current header node size
    if (pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        //Process remaining nodes
        pMergedHead->m_pNext = Merge1(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = Merge1(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}