将两个递增的有序链表合并为一个递增的有序链表。要求结果为开辟新的空间

算法思路：

1. 新建一个空链表作为合并后的链表；
2. 比较两个链表的头节点，将较小的节点加入到新链表中，并且将指针指向下一个节点；
3. 重复步骤 2 直到其中一个链表为空；
4. 将另一个非空链表的所有节点加入到新链表中；
5. 返回新链表。

算法实现：

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

def merge_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)  # 新链表的虚拟头节点
    cur = dummy  # 新链表的当前节点

    while l1 and l2:
        if l1.val < l2.val:
            cur.next = ListNode(l1.val)
            l1 = l1.next
        else:
            cur.next = ListNode(l2.val)
            l2 = l2.next
        cur = cur.next

    if l1:
        cur.next = l1
    else:
        cur.next = l2

    return dummy.next

算法分析：

时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是两个链表的长度，每个节点最多被遍历一次。

空间复杂度：$O(m+n)$，需要开辟新的空间来存储新链表。