将两个有序链表并为一个有序链表

算法思路：

创建一个新的链表，用于存储合并后的有序链表。同时定义两个指针，分别指向要合并的两个有序链表的头结点。比较两个指针指向的结点的值，将较小的结点添加到新链表中，并将指向较小结点的指针后移一位。重复此过程，直到其中一个链表为空，然后将另一个链表中剩余的结点全部添加到新链表的末尾。

算法实现：

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

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)  # 创建一个虚拟头结点
    cur = dummy  # 创建一个指针，指向新链表的末尾
    while l1 and l2:  # 只要两个链表都不为空，就比较它们的头结点
        if l1.val <= l2.val:
            cur.next = l1  # 将较小的结点添加到新链表的末尾
            l1 = l1.next  # 向后移动指向 l1 的指针
        else:
            cur.next = l2  # 将较小的结点添加到新链表的末尾
            l2 = l2.next  # 向后移动指向 l2 的指针
        cur = cur.next  # 向后移动指向新链表末尾的指针
    if l1:  # 如果 l1 还有剩余的结点，将它们全部添加到新链表的末尾
        cur.next = l1
    if l2:  # 如果 l2 还有剩余的结点，将它们全部添加到新链表的末尾
        cur.next = l2
    return dummy.next  # 返回新链表的头结点

时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是两个有序链表的长度。

空间复杂度：$O(1)$