21. 合并两个有序链表

Posted on Edited on In Views: Word count in article: 674 Reading time ≈ 1 mins.

21. 合并两个有序链表

题目链接：21. 合并两个有序链表

题目描述

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

核心思考：双指针与虚拟头节点

这是一道极其经典的链表基础操作题。因为两个链表本身已经是有序的了，所以我们可以直接使用双指针（或称归并排序的合并过程）的思路。

我们需要两个指针分别指向两个链表的当前节点，每次比较这两个节点的值：

  1. 取出两者中较小的那个节点。
  2. 将这个较小的节点接到我们正在构建的“结果链表”的末尾。
  3. 移动刚才被取出的节点所在链表的指针，使其指向下一个节点。
  4. 重复这个过程，直到其中一个链表被遍历完。
  5. 最后，只要把尚未遍历完的那个链表，整个儿直接拼接到结果链表的末尾即可。

虚拟头节点 (Dummy Node)：
在构建“结果链表”时，我们会面临一个边界问题：第一个放入结果链表的节点是谁？它没有前驱节点。为了避免在代码中写繁琐的 if 语句来特判头节点，链表题有一个常用的技巧——引入一个虚拟头节点 (Dummy Node)。
我们让一个永远不变的假节点作为链表的头部，所有的真实节点都挂在这个假节点之后。最后返回结果时，只需返回 Dummy.next 即可。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        Head = ListNode()
        curp = Head
        p_1 = list1
        p_2 = list2

        while p_1 is not None and p_2 is not None:
            if p_1.val > p_2.val:
                curp.next = p_2
                p_2 = p_2.next
            else:
                curp.next = p_1
                p_1 = p_1.next
            curp = curp.next
        
        if p_1 is not None:
            curp.next = p_1
        if p_2 is not None:
            curp.next = p_2
        
        return Head.next

复杂度分析

  • 时间复杂度：$O(m + n)$，其中 $m$ 和 $n$ 分别是两个链表的长度。在 while 循环中，每次我们都会把一个节点接入到合并后的链表中，因此最多执行 $m + n$ 次循环。
  • 空间复杂度：$O(1)$。我们仅仅用了几个常数级别的指针 (Head, curp, p_1, p_2) 用于追踪和连接现有的节点，并没有开辟任何与 m、n 大小相关的新空间。

image-compressed.png