剣指offer----2つの秩序あるチェーン時計を合併する

1758 ワード

テーマ:2つの増加した秩序チェーンテーブルをマージします.
注意:テスト時には、2つのチェーンテーブルが1つまたは2つ空いている場合に全面的に考慮する必要があります.
再帰的でない:
 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL)
            return pHead2;
        if(pHead2==NULL)
            return pHead1;
        ListNode* head=NULL;
        ListNode* cur=NULL;
        if(pHead1->val < pHead2->val)
        {
            
            cur=pHead1;
            head=cur;
            pHead1=pHead1->next;
        }
        else
        {
        	cur=pHead2;
            head=cur;
            pHead2=pHead2->next;
        }
        
        while(pHead1!=NULL&&pHead2!=NULL)
        {
        	if(pHead1->val < pHead2->val)
            {
             	cur->next=pHead1;
                pHead1=pHead1->next;
            }
            else
            {
            	cur->next=pHead2;
                pHead2=pHead2->next;
            }
            cur=cur->next;
            
        }
        if(pHead1!=NULL)	
        {
            cur->next=pHead1;
            
        }
        else
        {
        	cur->next=pHead2;    
            
        }
        return head;
    }

再帰:
 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL)
            return pHead2;
        if(pHead2==NULL)
            return pHead1;
        if(pHead1->val < pHead2->val)
        {
            
            pHead1->next=Merge(pHead1->next,pHead2);
            return pHead1;
          
        }
        else
        {
            pHead2->next=Merge(pHead1,pHead2->next);
            return pHead2;
            
        } 
    }
}