剣指offer-面接問題17:2つのソートされたチェーンテーブルをマージ

タイトル:2つのインクリメンタルソートのチェーンテーブルを入力し、この2つのチェーンテーブルをマージし、新しいチェーンテーブルのノードをインクリメンタルソートします.
考え方:2つのチェーンテーブルから新しいチェーンテーブルのノードとして小さいノードを選択するたびに、ここには2つの方法があり、ループまたは再帰があります.(1)ループは,2つのチェーンテーブルのうち小さいノードを取り出すたびに新しいチェーンテーブルに挿入し,そのうちの1つのチェーンテーブルの末尾ノードに達すると,もう1つのチェーンテーブルの残りの部分が直接この末尾ノードに接続される.(2)2つのチェーンテーブルの中から小さいテーブルを新しいチェーンテーブルのヘッダとして選択すると,残りの問題は2つの新しい並べ替えられたチェーンテーブルの結合であり,そのうちの1つのチェーンテーブルのヘッダが1つのノードを後方に移動しただけである.この2つの新しいチェーンテーブルのマージ手順は、従来と同様であり、典型的な再帰プロセスである.

//          ，   
ListNode* MergeSortedList(ListNode* pListHead1, ListNode* pListHead2)
{
    if(pListHead1 == NULL)
        return pListHead2;
    else if(pListHead2 == NULL)
        return pListHead1;
    else
    {
	ListNode* pNode1 = pListHead1;
	ListNode* pNode2 = pListHead2;
	ListNode* pLastNode = NULL;
	ListNode* NewHead = NULL;
	if(pListHead1->m_nValue < pListHead2->m_nValue)
	{
	    NewHead = pListHead1;
	    pNode1 = pNode1->m_pNext;
	}
	else
	{
	    NewHead = pListHead2;
	    pNode2 = pNode2->m_pNext;
	}
	pLastNode = NewHead;
		
	if (pNode1 == NULL)   
            pLastNode->m_pNext = pNode2;                
          
        if (pNode2 == NULL)   
            pLastNode->m_pNext = pNode1;            
    	
	while (pNode1 != NULL && pNode2 != NULL)  
    	{  
            if (pNode1->m_nValue < pNode2->m_nValue)  
            {     
        	pLastNode->m_pNext = pNode1;  
            	pLastNode = pNode1;  
            	pNode1 = pNode1->m_pNext;              
            }  
            else  
            {  
            	pLastNode->m_pNext = pNode2;  
            	pLastNode = pNode2;  
            	pNode2 = pNode2->m_pNext;              
            }  
  
            if (pNode1 == NULL)  
            	pLastNode->m_pNext = pNode2;                  
            if (pNode2 == NULL)  
            	pLastNode->m_pNext = pNode1;             
    	}
	return NewHead;
    }
}

再帰バージョン:

//          ，    
ListNode* MergeSortedList(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    if(pHead2 == NULL)
        return pHead1;
    
    ListNode* pMergedHead = NULL;
    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = MergeSortedList(pHead2->m_pNext, pHead1);
    }

    return pMergedHead;
}