合并两个有序链表

题目

题���链接

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

题目描述

代码实现

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 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步骤。