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

题目的主要信息：

两个元素值递增的链表，单个链表的长度为 $n$
合并这两个链表并使新链表中的节点仍然是递增排序的

举一反三：

学习完本题的思路你可以解决如下题目：

JZ23.链表中环的入口节点

JZ22.链表中倒数最后k个节点

JZ52.两个链表的第一个公共节点

方法一：双指针迭代（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

这道题既然两个链表已经是排好序的，都是从小到大的顺序，那我们要将其组合，可以使用归并排序的思想：每次比较两个头部，从中取出最小的元素，然后依次往后。这样两个链表依次往后，我们肯定需要两个指针同方向访问才能实现。

具体过程：

step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
step 2：新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
step 3：遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
step 4：遍历到最后肯定有一个链表还有剩余的节点，它们的值将大于前面所有的，直接连在新的链表后面即可。

图示：

alt

Java实现代码：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //一个已经为空了，直接返回另一个
        if(list1 == null) 
            return list2;
        if(list2 == null)
            return list1;
        //加一个表头
        ListNode head = new ListNode(0); 
        ListNode cur = head;
        //两个链表都要不为空
        while(list1 != null && list2 != null){ 
            //取较小值的节点
            if(list1.val <= list2.val){ 
                cur.next = list1;
                //只移动取值的指针
                list1 = list1.next; 
            }else{
                cur.next = list2;
                //只移动取值的指针
                list2 = list2.next; 
            }
            //指针后移
            cur = cur.next; 
        }
        //哪个链表还有剩，直接连在后面
        if(list1 != null) 
            cur.next = list1;
        else
            cur.next = list2;
        //返回值去掉表头
        return head.next; 
    }
}

C++实现代码：

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，直接返回另一个
        if(pHead1 == NULL) 
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        //加一个表头
        ListNode* head = new ListNode(0); 
        ListNode* cur = head;
        //两个链表都要不为空
        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;
        else
            cur->next = pHead2;
        //返回值去掉表头
        return head->next; 
    } 
};

Python代码实现：

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        #一个已经为空了，直接返回另一个
        if pHead1 == None: 
            return pHead2
        if pHead2 == None:
            return pHead1
        #加一个表头
        head = ListNode(0) 
        cur = head
        #两个链表都要不为空
        while pHead1 and 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
        else:
            cur.next = pHead2
        #返回值去掉表头
        return head.next

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况遍历两个链表共 $2 * n$ 个节点
空间复杂度： $O (1)$ ，无额外辅助空间使用，返回链表使用的是原有节点组装，未开辟空间

方法二：双指针递归（扩展思路）

思路：

上述方法一中，我们利用归并思想不断合并两个链表，每当我们添加完一个节点后，该节点指针后移，相当于这个链表剩余部分与另一个链表剩余部分合并，两个链表剩余部分合并就是原问题两个有序链表合并的子问题，因此也可以使用递归：

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

具体做法：

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

Java实现代码：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //一个已经为空了，返回另一个
        if(list1 == null) 
            return list2;
        if(list2 == null)
            return list1;
        //先用较小的值的节点
        if(list1.val <= list2.val){ 
            //递归往下
            list1.next = Merge(list1.next, list2); 
            return list1; 
        }else{
            //递归往下
            list2.next = Merge(list1, list2.next); 
            return list2;
        }
    }
}

C++实现代码：

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，返回另一个
        if(pHead1 == NULL) 
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        //先用较小的值的节点
        if(pHead1->val <= pHead2->val){ 
            //递归往下
            pHead1->next = Merge(pHead1->next, pHead2); 
            return pHead1; 
        }else{
            //递归往下
            pHead2->next = Merge(pHead1, pHead2->next); 
            return pHead2;
        }
    }
};

Python代码实现：

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        #一个已经为空了，返回另一个
        if pHead1 == None: 
            return pHead2
        if pHead2 == None:
            return pHead1
        #先用较小的值的节点
        if pHead1.val <= pHead2.val: 
            #递归往下
            pHead1.next = self.Merge(pHead1.next, pHead2) 
            return pHead1
        else:
            #递归往下
            pHead2.next = self.Merge(pHead1, pHead2.next) 
            return pHead2

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况遍历两个链表共 $2 n$ 个节点
空间复杂度： $O (n)$ ，递归栈深度最大为两个链表的长度和 $2 n$