给定两个链表，每个链表都已经按升序排列，设计算法实现将两个链表合并到一个升序链表中，返回合并后的链表，写出这段代码

以下是合并两个升序链表的代码：

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)
    curr = dummy
    
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    if l1:
        curr.next = l1
    elif l2:
        curr.next = l2
    
    return dummy.next

该算法的时间复杂度为 O(m+n)，其中 m 和 n 分别为两个链表的长度。

相关问题

给定两个链表，每个链表都已经按升序排列，设计算法实现将两个链表合并到一个升序链表中，返回合并后的链表。

可以使用双指针法，分别指向两个链表的头节点，比较两个节点的值，将较小的节点加入到新的链表中，并将指针向后移动。直到其中一个链表为空，将另一个链表剩余的节点加入到新的链表中即可。最后返回新的链表即为合并后的升序链表。