21. 合并两个有序链表

21. 合并两个有序链表
你的 mergeTwoLists 函数用于合并两个已排序的链表。代码中存在缩进错误和一些细节问题。以下是修正后的代码以及详细注释：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    # 创建一个哑节点(dummy node)并初始化指针
    dummy = ListNode(0)
    temp = dummy

    # 遍历两个链表，直到其中一个为空
    while l1 and l2:
        if l1.val <= l2.val:
            temp.next = l1
            l1 = l1.next
        else:
            temp.next = l2
            l2 = l2.next
        temp = temp.next

    # 将剩余的节点连接到结果链表
    temp.next = l1 if l1 else l2

    # 返回合并后的链表头节点
    return dummy.next

详细注释

1. 定义链表节点类：

   class ListNode:
       def __init__(self, val=0, next=None):
           self.val = val
           self.next = next
   

2. 合并两个有序链表的函数：

   def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
   

3. 创建哑节点：

   dummy = ListNode(0)
   temp = dummy
   

   • 创建一个哑节点 dummy，并初始化指针 temp 指向 dummy。哑节点用于简化链表操作，最终返回合并后的链表头节点。

4. 遍历两个链表，直到其中一个为空：

   while l1 and l2:
       if l1.val <= l2.val:
           temp.next = l1
           l1 = l1.next
       else:
           temp.next = l2
           l2 = l2.next
       temp = temp.next
   

   • 比较 l1 和 l2 的当前节点值，将较小值的节点连接到结果链表 temp 的 next，并移动相应链表的指针。
   • 移动 temp 指针到下一个节点。

5. 连接剩余的节点：

   temp.next = l1 if l1 else l2
   

   • 如果 l1 或 l2 还有剩余的节点，直接连接到 temp 的 next。

6. 返回合并后的链表头节点：

   return dummy.next
   

   • 返回哑节点 dummy 的 next，即合并后的链表头节点。

示例

假设链表 l1 为 1 -> 2 -> 4，链表 l2 为 1 -> 3 -> 4。

1. 初始状态：

   • dummy: 0 -> None
   • temp 指向 dummy

2. 第一次比较：

   • l1.val = 1, l2.val = 1
   • 将 l1 连接到 temp.next，移动 l1 到下一个节点
   • dummy: 0 -> 1 -> 2 -> 4
   • temp: 1 -> 2 -> 4

3. 第二次比较：

   • l1.val = 2, l2.val = 1
   • 将 l2 连接到 temp.next，移动 l2 到下一个节点
   • dummy: 0 -> 1 -> 1 -> 3 -> 4
   • temp: 1 -> 1 -> 3 -> 4

4. 继续比较并合并：

   • 继续上述过程，直到 l1 和 l2 中一个为空

5. 连接剩余的节点：

   • 将剩余的 l1 或 l2 连接到 temp.next
   • 最终 dummy 连接的链表为 0 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4

6. 返回合并后的链表头节点：

   • 返回 dummy.next 即 1 -> 1 -> 2 -> 3 -> 4 -> 4

通过这种方式，可以将两个有序链表合并为一个新的有序链表。