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

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode *mainList, *cur, *tmp;  //mainList为 第一个元素较小的链表
    struct ListNode *insertList;            //insertList为 第一个元素较大的链表
    if(!pHead1 && pHead2)   return pHead2;  //特殊输入处理
    if(!pHead2 && pHead1)   return pHead1;
    if(!pHead2 && !pHead1)  return NULL;
    if(pHead1->val <= pHead2->val){         //判断一个元素的大小，将pHead1\2赋值给mainlist insertlist
        mainList = pHead1, insertList = pHead2;
    }else{
        mainList = pHead2, insertList = pHead1;
    }
    cur = mainList;                         //当前指针

    while(cur->next || insertList){         //只要当前元素和插入链表 有任一是存在的，则进行循环
        if(!cur->next && insertList){       //mainlist的已经到末尾了，则直接插入insertList的值并退出
            cur->next = insertList;         //这里不需要考虑insertList的值是否大于cur，因为由前面赋值mainList insertList的
            break;                          //  逻辑可知insertList的值必小于cur
        }else if(!insertList){              //当insertList不存在，则退出
            break;
        }else if(cur->next && insertList && cur->next->val > insertList->val){
            tmp = cur->next;                //当cur的下一个值存在且insertList存在，则判断insert的值是否小于cur->next的值
            cur->next = insertList;         // 小于则进行插入
            insertList = insertList->next;
            cur = cur->next;                //cur指向插入的值
            cur->next = tmp;                //将插入的值next指向原来cur的next
        }else{
            cur = cur->next;                //当cur的下一个值存在且insertList存在，且insert的值大于cur->next的值
        }                                   //则cur移到下一个
    }
    return mainList;
}