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

题目链接

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围: 单个链表的长度 $n$ 满足 $0 \le n \le 1000$ 。要求: 空间复杂度 $\mathcal{O}(1)$ ，时间复杂度 $\mathcal{O}(n+m)$ ，其中 $n$ 和 $m$ 分别为两个链表的长度。

示例: 输入: {1,3,5},{2,4,6}

输出: {1,2,3,4,5,6}

解题思路

这个问题的目标是在不破坏排序规则的前提下，将两个链表"编织"在一起。我们可以使用两种经典的方法：迭代或递归。迭代法在空间上更优，符合题目 $\mathcal{O}(1)$ 的要求。

方法一：迭代 (推荐)

这个方法利用一个虚拟头节点和一个尾指针来构建新的合并链表。

算法步骤:

初始化:
- 创建一个虚拟头节点 dummy。这能极大地简化代码，避免对新链表的头节点进行特殊处理。
- 创建一个尾指针 tail，初始时指向 dummy。tail 将永远指向新链表的最后一个节点。
- 创建两个指针 p1 和 p2，分别指向两个输入链表的头 pHead1 和 pHead2。
主循环:
- 当 p1 和 p2 都不为空时，进行比较： a. 如果 p1.val <= p2.val，说明 p1 指向的节点应该被添加到新链表中。 - 将 tail.next 指向 p1。 - p1 指针向后移动一位。 b. 否则 (p1.val > p2.val)，说明 p2 指向的节点更小。 - 将 tail.next 指向 p2。 - p2 指针向后移动一位。
- 在每一步之后，都必须将 tail 指针也向后移动一位，使其始终指向新链表的末尾。
处理剩余部分:
- 当循环结束时，p1 和 p2 中最多只有一个还不为空。这个非空的链表剩下的所有节点，都已经排好序且大于等于新链表中已有的所有节点。
- 因此，我们直接将 tail.next 指向这个剩下的链表即可。
返回:
- dummy 节点的 next 指针指向的，就是合并后链表的真正头节点。返回 dummy.next。

方法二：递归

递归的思路更简洁，但会消耗栈空间。

基准情况: 如果一个链表为空，返回另一个链表。
递归步骤: 比较两个链表头节点的值。
- 如果 pHead1.val 更小，则 pHead1 是新链表的头，其 next 应该是 pHead1.next 和 pHead2 合并后的结果。
- 反之，pHead2 是新链表的头，其 next 应该是 pHead1 和 pHead2.next 合并后的结果。

代码

cpp
java
python

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        ListNode* dummy = new ListNode(0); // 虚拟头节点
        ListNode* tail = dummy;
        
        while (pHead1 != nullptr && pHead2 != nullptr) {
            if (pHead1->val <= pHead2->val) {
                tail->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                tail->next = pHead2;
                pHead2 = pHead2->next;
            }
            tail = tail->next;
        }
        
        // 连接剩余的链表部分
        tail->next = (pHead1 != nullptr) ? pHead1 : pHead2;
        
        ListNode* head = dummy->next;
        delete dummy;
        return head;
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    public ListNode Merge(ListNode pHead1, ListNode pHead2) {
        // write code here
        ListNode dummy = new ListNode(0); // 虚拟头节点
        ListNode tail = dummy;
        
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                tail.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                tail.next = pHead2;
                pHead2 = pHead2.next;
            }
            tail = tail.next;
        }
        
        // 连接剩余的链表部分
        tail.next = (pHead1 != null) ? pHead1 : pHead2;
        
        return dummy.next;
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def Merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        dummy = ListNode(0) # 虚拟头节点
        tail = dummy
        
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                tail.next = pHead1
                pHead1 = pHead1.next
            else:
                tail.next = pHead2
                pHead2 = pHead2.next
            tail = tail.next
            
        # 连接剩余的链表部分
        tail.next = pHead1 if pHead1 else pHead2
        
        return dummy.next

算法及复杂度

算法: 迭代 (双指针)
时间复杂度: $\mathcal{O}(N+M)$ ，其中 $N$ 和 $M$ 分别为两个链表的长度。因为我们最多遍历两个链表的所有节点一次。
空间复杂度: $\mathcal{O}(1)$ 。我们没有创建新的节点，只是重新连接了现有节点，只使用了常数个额外指针。