题目

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

---

示例

• 示例 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 <= 100
• l1 和 l2 均按 非递减顺序 排列

---

思路及算法代码

思路

我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

算法

首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:  
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:  
        # 创建一个虚拟头节点prehead，它的值不重要，主要用于简化链表头部插入操作  
        prehead = ListNode(-1)  
  
        # prev指针用于遍历合并后的链表，初始时指向虚拟头节点  
        prev = prehead  
  
        # 当l1和l2都不为空时，循环比较它们的值  
        while l1 and l2:  
            # 如果l1的值小于等于l2的值  
            if l1.val <= l2.val:  
                # 将l1节点插入到prev之后  
                prev.next = l1  
                # 移动l1指针到下一个节点  
                l1 = l1.next  
            else:  
                # 如果l1的值大于l2的值，则插入l2节点  
                prev.next = l2  
                # 移动l2指针到下一个节点  
                l2 = l2.next  
            # 将prev指针移动到新插入的节点  
            prev = prev.next  
  
        # 当退出循环时，l1和l2中至少有一个为空  
        # 直接将prev的next指向非空链表，因为合并后的链表已经是有序的  
        prev.next = l1 if l1 is not None else l2  
  
        # 返回合并后链表的头节点，即虚拟头节点的下一个节点  
        return prehead.next

---

复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

---

知识点

prehead = ListNode(-1) 创建了一个名为 prehead 的虚拟头节点（dummy head node），并将其初始化为一个 ListNode 类型的对象，其值为 -1。这个虚拟头节点不是最终合并链表的一部分，而是作为一个辅助节点，用来简化链表节点的插入操作。