合并两个有序列表的循环和递归实现

// 方法一， 循环实现
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;
    ListNode* pCurNode = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pHead1 = pHead1->m_pNext;
    }
    else
    {
        pMergedHead = pHead2;
        pHead2 = pHead2->m_pNext;
    }

    for (pCurNode = pMergedHead; (NULL != pHead1) && (NULL != pHead2); )
    {
        if(pHead1->m_nValue < pHead2->m_nValue)
        {
            pCurNode->m_pNext = pHead1;
            pCurNode = pHead1;
            pHead1 = pHead1->m_pNext;
        }
        else
        {
            pCurNode->m_pNext = pHead2;
            pCurNode = pHead2;
            pHead2 = pHead1->m_pNext;
        }
    }

    pCurNode->m_pNext = (NULL == pHead1) ? pHead2 : pHead1;

    return pMergedHead;
}

// 方法二，递归实现
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = Merge(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}