leetcode_链表 21.合并两个有序链表

21.合并两个有序链表

• 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
• 思路：
  1. 定义一个哑节点（dummy node），哑节点是一个初始的虚拟节点，它不存储有效值，只是方便操作，定义一个指针 current 指向哑节点，用于构建新链表。
  2. 遍历两个链表，使用两个指针 p1 和 p2 分别指向 list1 和 list2 的头部，并比较 p1.val 和 p2.val，将较小值的节点连接到 current.next。
  3. 处理剩余部分，当一个链表遍历完后，将另一个链表的剩余部分直接连接到 current.next。
  4. 返回结果，最终返回哑节点的下一个节点 dummy.next，即为合并后的链表头。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
 # 定义哑节点和当前指针
        dummy = ListNode(-1)  # 哑节点，初始值无意义
        current = dummy

        # 遍历两个链表
        while list1 and list2:
            if list1.val <= list2.val:  # 比较两个链表当前节点的值
                current.next = list1  # 将list1当前节点连接到结果链表
                list1 = list1.next  # 移动list1指针
            else:
                current.next = list2  # 将list2当前节点连接到结果链表
                list2 = list2.next  # 移动list2指针
            current = current.next  # 移动结果链表指针

        # 处理剩余部分
        if list1:  # 如果list1还有节点
            current.next = list1
        if list2:  # 如果list2还有节点
            current.next = list2

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

        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """

• 时间复杂度：O(m+n)
  • 每次操作一个节点，总共需要遍历两个链表的所有节点，即时间复杂度为 O(n + m)，其中 n 和 m 是两个链表的长度。
• 空间复杂度：O(1)