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

链表-合并有序链表序列

心思想：

1. 判空，任意一个为空，则返回另一个
2. 定义新链表头和新链表的哨兵指针
3. 给2定义的链表头和哨兵赋值：需从两个非空链表抉择出来一个小者结点
4. 遍历两个链表，任意一个为空了，则结束
   • 判断出小的结点，追加到新链表结点的哨兵尾，且移动哨兵结点
   • 被摘掉的链表往后移一步
5. 粘贴新链表和结束前人一个非空的链表
6. 返回

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    // 分别判断是否为空
    if(pHead1 == NULL)
    {
        return pHead2;
    }
        
    if(pHead2 == NULL)
    {
        return pHead1;
    }
    
    // 排序,此刻两个不为空的链表，以pHead1为基准
    struct ListNode * newHead=NULL;
    struct ListNode * curr=NULL;
    
    if(pHead1->val > pHead2->val)
    {
        newHead=pHead2;
        curr=pHead2;
        pHead2=pHead2->next;
    }
    else
    {
        newHead=pHead1;
        curr=pHead1;
        pHead1=pHead1->next;        
    }

    // 遍历两个node节点，挨个节点判断纳入新节点
    // 注意摘节点的步骤
    while(pHead1 != NULL && pHead2 != NULL )
    {
        if(pHead1->val < pHead2->val)
        {
            // 摘取小的结点
            curr->next = pHead1;
            curr=pHead1;
            pHead1=pHead1->next;
        }
        else
        {
            curr->next = pHead2;
            curr=pHead2;
            pHead2=pHead2->next;
        }
    }
    
    // 剩余谁是null
    if(pHead1 == NULL)
    {
        curr->next = pHead2;
    }
    else
    {
        curr->next = pHead1;
    }
    
    return newHead;
}