21. 合并两个有序链表

一、题目概述

本题要求将两个升序链表合并为一个新的升序链表，新链表由给定的两个链表的所有节点拼接而成

二、代码实现

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
28
# 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]:
        # 创建虚拟头节点
        dummy = ListNode()
        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

        # 处理剩余节点
        if list1:
            current.next = list1
        if list2:
            current.next = list2

        return dummy.next

三、解题思路及步骤分析

（一）整体思路

通过依次比较两个链表中的节点值，将较小值的节点逐个连接到一个新创建的链表上，直至其中一个链表遍历完，再把剩余链表的节点全部连接到新链表的末尾，最终得到合并后的升序链表。

（二）具体步骤

  1. 创建虚拟头节点与指针初始化：
    • 首先创建一个虚拟头节点 dummy（值通常为默认值，如 0），它主要用于方便后续链表操作，并不属于最终有效的链表节点。
    • 同时将指针 current 初始化为指向这个虚拟头节点，该指针会在后续构建新链表的过程中不断移动，用于确定新节点的连接位置。
  2. 比较并连接节点：
    • 在 while list1 and list2: 循环中：
      • 当 list1.val <= list2.val 时：
        • 把 list1 当前节点连接到新链表（通过 current.next = list1），此时新节点连接在 current 所指节点之后。
        • 然后将 list1 指针移动到下一个节点（list1 = list1.next），以便下一次比较。
      • 当 list1.val > list2.val（即 else 分支）：
        • 把 list2 当前节点连接到新链表（current.next = list2）。
        • 接着将 list2 指针移动到下一个节点（list2 = list2.next）。
      • 每次完成节点连接后，都要将 current 指针移动到新连接的节点上（current = current.next），这样才能在后续继续连接新的节点到正确位置。
  3. 处理剩余节点：
    • 当 while 循环结束后，可能存在其中一个链表还有剩余节点的情况。
    • 如果 list1 还有剩余节点（if list1:），就将 list1 剩余的所有节点连接到新链表的末尾（current.next = list1）。
    • 同理，如果 list2 还有剩余节点（if list2:），则将 list2 剩余的所有节点连接到新链表的末尾（current.next = list2）。
  4. 返回合并后的链表：
    • 最后要返回的是合并后的升序链表，由于 dummy 是虚拟头节点，真正的合并后链表是从 dummy 下一个节点开始的，所以返回 dummy.next。注意最初若错误地返回 current.next 是不对的，因为 current 在处理完剩余节点后已经指向合并后链表的末尾，而不是起始节点。