Easy

题目描述

给你两个有序链表的头节点 list1 和 list2。

请你将两个链表合并为一个有序链表。新链表应该通过拼接给定的两个链表的所有节点组成。

返回合并后链表的头节点。

示例 1：

输入：list1 = [1,2,4], list2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：list1 = [], list2 = []
输出：[]

示例 3：

输入：list1 = [], list2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • list1 和 list2 均按 非递减顺序 排列

解题思路

这道题有两种经典的解法：

解法一：迭代法（推荐） 创建一个虚拟头节点 dummy，用指针 current 指向当前结果链表的末尾。同时用两个指针分别遍历两个链表，每次比较两个指针指向节点的值，选择较小的节点加入结果链表，并移动对应指针。当其中一个链表遍历完成后，将另一个链表的剩余部分直接连接到结果链表末尾。

解法二：递归法 递归思想：如果 list1 的值小于等于 list2 的值，那么 list1 的头节点就是合并后链表的头节点，剩余部分是 list1.next 与 list2 的合并结果。递归的终止条件是其中一个链表为空，此时直接返回另一个链表。

两种方法的时间复杂度都是 O(m+n)，但迭代法的空间复杂度更优。迭代法使用虚拟头节点的技巧可以简化边界处理，避免特殊判断第一个节点的情况。

代码实现

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        
        current->next = list1 ? list1 : list2;
        
        return dummy.next;
    }
};

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        current = dummy
        
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        
        current.next = list1 if list1 else list2
        
        return dummy.next

public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        current.next = list1 != null ? list1 : list2;
        
        return dummy.next;
    }
}

var mergeTwoLists = function(list1, list2) {
    let dummy = new ListNode(0);
    let current = dummy;
    
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    current.next = list1 || list2;
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型迭代法递归法
时间复杂度O(m+n)O(m+n)
空间复杂度O(1)O(m+n)

其中 m 和 n 分别是两个链表的长度。递归法的空间复杂度为 O(m+n) 是由于递归调用栈的深度。

相关题目