合并单链表的时间复杂度

### 合并单链表的时间复杂度分析

当讨论合并两个有序单链表的操作时，时间复杂度主要取决于遍历这两个链表的过程。对于长度分别为 \(n\) 和 \(m\) 的两个有序单链表，在每次循环迭代中只会有一个元素被加入到新的合并后的链表中[^2]。

由于每一次比较操作之后都会从至少一个输入列表中移除一项，直到所有项都被处理完毕为止，这意味着总的比较次数等于两链表节点数量之和。因此，整个过程中的基本运算次数与\(n+m\)成正比，即线性关系。所以，合并两个有序单链表的时间复杂度为 \(O(n + m)\)。

具体来说，这个算法通过同时遍历两个链表来构建一个新的已排序链表。每当遇到较小的那个节点就将其添加至结果链表，并继续前进该链表上的指针。一旦其中一个链表完全遍历结束，则只需简单地附加剩余未遍历部分即可完成全部工作。这种策略确保了即使是最坏情况下也能达到最优性能表现。

def merge_two_lists(l1, l2):
    dummy = ListNode()
    current = dummy
    
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
        
    # Attach the remaining part of non-empty list.
    current.next = l1 or l2
    
    return dummy.next