题目

题目链接

合并两个排序的链表_牛客题霸_牛客网

题目描述

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if(pHead1 == nullptr)
            return pHead2;
        if(pHead2 == nullptr)
            return pHead1;
        ListNode *newHead = new ListNode(-1), *phead = newHead;
        while(pHead1 && pHead2){
            if(pHead1->val < pHead2->val){
                phead->next = pHead1;
                pHead1 = pHead1->next;
            }
            else{
                phead->next = pHead2;
                pHead2 = pHead2->next;
            }
            phead = phead->next;
        }
        phead->next = pHead1 != nullptr ? pHead1 : pHead2;
        return newHead->next;
    }
};

题目分析

1、首先构造一个哨兵位节点，避免头节点的分类讨论

2、比较两个头节点中值的较小者，挂在哨兵位节点后边。这里还需要构造一个临时节点phead随着新链表的移动（可以理解为新链表尾插节点）。

3、在将较小节点挂在哨兵位节点之后，较小值的链表的头节点也需要向后移动，还有新链表中的phead临时节点也需要移动，即始终是新链表的尾节点。

4、这里的2、3步骤是重复进行的，当其中一个链表的节点全挂在新链表后面后，就需要考虑一种情况了。就是其中一个链表的节点挂完了，但是另外的一个链表却没有。而且这两个链表是有序的，所以可以直接将新链表的phead临时节点指向未挂完的链表后边。

5、最后，还得考虑两个链表的输入情况。即当两个链表中有一个链表是空的，即只用返回另外一个链表即可。

下边的图示演示的是上边的2和3步骤。