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

第一种方法：双指针迭代

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* phead = new ListNode(0); //用于生成新链表的头结点（phead->next），val为0
        ListNode* cur = phead;
        //特殊情况处理
        if (pHead1 == nullptr)
            return pHead2;
        if (pHead2 == nullptr)
            return pHead1;

        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        //哪个链表还有剩，直接连在后面
        if (pHead1)
            cur->next = pHead1;
        if (pHead2)
            cur->next = pHead2;
        //返回合并后的链表的头结点
        return phead->next;
    }
};

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* phead; //设置一个节点作为合并后新链表的头结点
        //特殊情况处理
        if (pHead1 == nullptr)
            return pHead2;
        if (pHead2 == nullptr)
            return pHead1;
        //为新链表的头结点赋值
        if (pHead1->val < pHead2->val) {
            phead = pHead1;
            pHead1 = pHead1->next;
        } else {
            phead = pHead2;
            pHead2 = pHead2->next;
        }
        ListNode* cur = phead; //用于新链表的生成

        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        //哪个链表还有剩，直接连在后面
        if (pHead1)
            cur->next = pHead1;
        if (pHead2)
            cur->next = pHead2;
        //返回合并后的链表的头结点
        return phead;
    }
};

写法一相比写法二省略了一次头结点的赋值。

第一种方法：双指针递归

不符合题目要求，提供出来开阔视野

时间复杂度：o(n)

空间复杂度：o(n)

• 终止条件： 当一个链表已经因为递归到了末尾，另一个链表剩余部分一定都大于前面的，因此我们可以将另一个链表剩余部分拼在结果后面，结束递归。
• 返回值： 每次返回拼接好的较大部分的子链表。
• 本级任务： 每级不断进入下一个较小的值后的链表部分与另一个链表剩余部分，再将本次的节点接在后面较大值拼好的结果前面。

具体做法：

• step 1：每次比较两个链表当前节点的值，然后取较小值的链表指针往后，另一个不变，两段子链表作为新的链表送入递归中。
• step 2：递归回来的结果我们要加在当前较小值的节点后面，相当于不断在较小值后面添加节点。
• step 3：递归的终止是两个链表有一个为空。

把问题拆解为，当前节点和更新后的两个链表进行合并

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //特殊情况处理
        if (pHead1 == nullptr)
            return pHead2;
        if (pHead2 == nullptr)
            return pHead1;
        //递归
        if (pHead1->val < pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};