当前位置：首页 > article >正文

LeetCode【0021】合并两个有序链表

article 2024/11/14 6:35:55

本文目录

1 中文题目
2 求解方法：双指针+虚拟头节点
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
3 题目总结

1 中文题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
在这里插入图片描述

链表如上
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
$\leq Node.val \leq 100$
l1 和 l2 均按 非递减顺序 排列

2 求解方法：双指针+虚拟头节点

2.1 方法思路

方法核心

使用虚拟头节点简化边界情况处理
采用双指针遍历两个链表并比较节点值
直接利用原有节点进行链接，不创建新节点

实现步骤

(1)初始化阶段：

创建虚拟头节点
初始化当前指针current

(2)合并主循环：

比较两个链表当前节点值
选择较小值的节点连接到新链表
移动对应链表的指针

(3)处理剩余节点：

检查是否有剩余节点
将剩余节点直接连接到结果链表

(4)返回结果：

返回虚拟头节点的next

方法示例

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

步骤演示：
1. 初始状态：
dummy -> NULL
current = dummy
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

2. 第一次比较（1 vs 1）：
dummy -> 1
current
list1: 2 -> 4
list2: 1 -> 3 -> 4

3. 第二次比较（2 vs 1）：
dummy -> 1 -> 1
           current
list1: 2 -> 4
list2: 3 -> 4

4. 第三次比较（2 vs 3）：
dummy -> 1 -> 1 -> 2
                current
list1: 4
list2: 3 -> 4

5. 第四次比较（4 vs 3）：
dummy -> 1 -> 1 -> 2 -> 3
                     current
list1: 4
list2: 4

6. 第五次比较（4 vs 4）：
dummy -> 1 -> 1 -> 2 -> 3 -> 4
                          current
list1: NULL
list2: 4

7. 处理剩余节点：
dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4
                               current

8. 最终返回：
1 -> 1 -> 2 -> 3 -> 4 -> 4

2.2 Python代码

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 创建虚拟头节点，简化边界情况处理
        dummy = ListNode(0)
        # 当前节点指针，用于构建新链表
        current = dummy
        
        # 当两个链表都不为空时，比较节点值并连接
        while list1 and list2:
            # 如果list1当前节点值较小
            if list1.val <= list2.val:
                # 将current的next指向list1当前节点
                current.next = list1
                # list1指针后移
                list1 = list1.next
            # 如果list2当前节点值较小
            else:
                # 将current的next指向list2当前节点
                current.next = list2
                # list2指针后移
                list2 = list2.next
            # current指针后移，准备下一次连接
            current = current.next
        
        # 处理剩余节点
        # 如果list1还有剩余，直接接在current后面
        if list1:
            current.next = list1
        # 如果list2还有剩余，直接接在current后面
        if list2:
            current.next = list2
        
        # 返回真实的头节点
        return dummy.next