题解 | #合并两个排序的链表#

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) { } };/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* p1=pHead1,*p2=pHead2;

    if(p1==nullptr||p2==nullptr)
    {
        if(p1==nullptr&&p2==nullptr)
        {
            return p1;
        }
        else if(p1==nullptr)
        {
            return p2;
        }
        else
            return p1;
    }
    
    ListNode* tmp=nullptr;
    ListNode* p=nullptr;
    
    int i;                       //设置互斥变量i，以确保字符串有序合并
    if(p1->val<=p2->val)
    {
        p=p1;             //若p1链表第一个元素小，以此为返回链表，i=1表示此时链表p末尾结点在链表1上
        i=1;
    }
    else                  //若p2链表第一个元素小，以p2为返回链表，i=2表示链表p末尾结点在链表2上
    {
        p=p2;
        i=2;
    }
    
    
    
    while((p1!=nullptr)&&(p2!=nullptr))           //若某一个链表遍历完，退出比较的循环
    {
        if((p1->val<=p2->val)&&i==1)      //为防止p1.val与p2.val相等时，链表串序，使用互斥量i
        {
            if(p1->next!=NULL)
            {
              if((p1->next->val)<=(p2->val))
               {
                  p1=p1->next;
               }
              else
              {
                 tmp=p1->next;
                 p1->next=p2;
                 p1=tmp;
                 i=2;
              
               }
            }
            else
            {
                 tmp=p1->next;
                 p1->next=p2;
                 p1=tmp;
                 i=2;
              
            }
        }
        else if((p1->val>=p2->val)&&i==2)
        {
            if(p2->next!=NULL)
            {
              if((p2->next->val)<=(p1->val))
               {
                  p2=p2->next;
               }
              else
              {
                 tmp=p2->next;
                 p2->next=p1;
                 p2=tmp;
                  i=1;
              
               }
            }
            else
            {
                 tmp=p2->next;
                 p2->next=p1;
                 p2=tmp;
                 i=1;
              
            }

        }
    }
    
    return p;
}

};