难度: Easy
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
Submission
运行时间: 48 ms
内存: 17 MB
# 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()
p = dummy
while list1 or list2:
if not list1:
p.next = ListNode(list2.val)
list2 = list2.next
elif not list2:
p.next = ListNode(list1.val)
list1 = list1.next
else:
if list1.val <= list2.val:
p.next = ListNode(list1.val)
list1 = list1.next
else:
p.next = ListNode(list2.val)
list2 = list2.next
p = p.next
return dummy.next
Explain
该题解使用了双指针的方法来合并两个有序链表。具体思路如下： 1. 创建一个虚拟头节点 dummy，使用指针 p 指向 dummy。 2. 同时遍历两个链表 list1 和 list2，比较当前节点的值，将较小的节点接到 p 指针后面。 3. 移动对应链表的指针到下一个节点。 4. 移动 p 指针到新接入的节点。 5. 重复步骤 2-4，直到其中一个链表遍历完毕。 6. 将剩余未遍历完的链表接到 p 指针后面。 7. 返回 dummy 的下一个节点，即合并后的链表的头节点。
时间复杂度: O(m+n)
空间复杂度: O(1)
# 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()
p = dummy
# 同时遍历两个链表
while list1 or list2:
# 如果 list1 遍历完毕，将 list2 的当前节点接到新链表后面
if not list1:
p.next = ListNode(list2.val)
list2 = list2.next
# 如果 list2 遍历完毕，将 list1 的当前节点接到新链表后面
elif not list2:
p.next = ListNode(list1.val)
list1 = list1.next
# 比较当前节点的值，选择较小的节点接到新链表后面
else:
if list1.val <= list2.val:
p.next = ListNode(list1.val)
list1 = list1.next
else:
p.next = ListNode(list2.val)
list2 = list2.next
# 移动 p 指针到新接入的节点
p = p.next
# 返回合并后的链表的头节点
return dummy.next
Explore
在实际的LeetCode题解中，直接创建新的ListNode确实看起来是一种选择，但这种方式可能会导致混淆。理想的处理方法是直接将剩余的链表接到p指针后面，以避免额外的空间占用和不必要的节点复制。实际代码中应直接将剩余链表接到p后，例如：p.next = list1 或 p.next = list2，这样更加高效，因为不需要逐个节点复制剩余链表。
当两个链表的节点值相等时，选择哪个链表的节点接到新链表后面通常基于一致性和简洁性的考虑，通常没有固定规则。因为两个节点值相同，接入哪一个都不会影响最终链表的顺序性或正确性。示例中如果先接list1，就继续这一策略，保持代码的一致性。
双指针方法处理合并两个有序链表的效率主要取决于两个链表的总节点数，即时间复杂度为O(m+n)，其中m和n分别是两个链表的长度。即使链表长度差异很大，算法的效率主要受较长链表的长度影响，但总体时间复杂度不会变。因此，长度差异虽存在，不会额外影响算法的效率。
虚拟头节点 dummy 的主要目的是简化链表操作，避免处理头节点为空的特殊情况，使得链表合并逻辑更清晰、更统一。不使用虚拟头节点时，算法需要额外的条件判断来初始化合并后的链表头节点，并在每次插入时判断当前链表是否为空，增加代码复杂度。
实际上，在合并链表时应避免创建新的ListNode实例，而是应该直接调整原有链表节点的指针，以保持空间复杂度为O(1)。这样不会修改原链表结构。如果要保持原链表结构不变，则需要创建新链表的每个节点的副本，这样会增加空间复杂度到O(m+n)。
返回dummy的下一个节点是一种常用的处理方式，以确保能正确返回合并后的头节点。当两个输入链表都为空时，dummy的下一个节点也会是空，这恰恰正确地表示了合并后链表也为空的情况，因此不会导致错误或异常。