2つの単調に増加するチェーンテーブルを入力し、2つのチェーンテーブルの合成後のチェーンテーブルを出力します.もちろん、合成後のチェーンテーブルは単調で減少しない規則を満たす必要があります.

タイトル:2つの単調に増加するチェーンテーブルを入力して、2つのチェーンテーブルの合成後のチェーンテーブルを出力して、もちろん私達は合成後のチェーンテーブルが単調で減らない規則を満たす必要があります
解析:まず、2つのチェーンテーブルの最初の要素の小さいノードを探して新しいチェーンテーブルのヘッダを作成し、2つのチェーンテーブルの要素を順番に比較し、小さなテールを新しいチェーンテーブルに挿入します(テールポインタを使用して新しいチェーンテーブルのテールをマークします).1つが終わると、もう1つの(つまり、残りの要素があるチェーンテーブル)の間に新しいチェーンテーブルのテールに掛けます.

 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        //        ，         
        if(pHead1==nullptr)
            return pHead2;
        else if(pHead2==nullptr)
            return pHead1;
        
        ListNode* head;//     
        ListNode* tail;//     
        
        //            ，        
        if(pHead1->valval)
        {
            head=pHead1;
            pHead1=pHead1->next;
        }
        else
        {
            head=pHead2;
            pHead2=pHead2->next;
        }
        tail=head;//      tail        
        
        //          (    ，                  )
        while(pHead2 && pHead1)
        {
            if(pHead1->valval)
            {
                tail->next=pHead1;
                pHead1=pHead1->next;
            }
            else
            {
                tail->next=pHead2;
                pHead2=pHead2->next;
            }
            //        ，         tail  
            tail=tail->next;
        }
        
        //   ，           ，                tail   
        if(pHead1!=nullptr)
        {
            tail->next=pHead1;
        }
        if(pHead2!=nullptr)
        {
            tail->next=pHead2;
        }
        
        return head;//         
    }