Python实现有序链表合并：合并操作与时间复杂度分析

合并两个有序链表是一个经典的编程问题，涉及到了数据结构和算法的运用。这个问题的目标是将两个已排序的链表（每个节点包含一个整数值）合并成一个新的有序链表。在这个任务中，我们通常假定链表的节点值是升序排列的。这里展示的是一个使用Python语言实现的解决方案。 首先，我们定义了一个链表节点类`ListNode`，它有两个属性：`val`用于存储节点的整数值，`next`指向链表的下一个节点。链表节点的初始化函数`__init__`设置了这两个默认值。 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` `mergeTwoLists`函数是核心部分，接收两个有序链表的头节点`l1`和`l2`作为参数，返回合并后的有序链表的头节点。为了处理链表合并，我们创建了一个哑节点`dummy`，其`val`为0，用作新链表的起始位置，`next`初始指向`None`。`current`变量则用来跟踪当前正在处理的新链表部分。 函数通过`while`循环遍历两个链表，同时比较节点值。如果`l1`的节点值小于`l2`，就将`l1`的节点添加到新链表，然后将`l1`向前移动；反之，将`l2`的节点添加。在每次迭代中，`current`都更新为其下一个节点，直到遍历完其中一个链表。 ```python def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: # ... 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 # ... ``` 遍历结束后，将未遍历完的链表剩余部分（如果有）连接到新链表的末尾。最后，返回哑节点的`next`属性，即合并后的有序链表的头节点。 这个解决方案具有时间复杂度O(n + m)，其中n和m分别代表两个输入链表的长度，因为需要遍历每个链表一次。空间复杂度是O(1)，仅使用了固定大小的内存来存储哑节点和指针，与链表长度无关。这个方法巧妙地利用了链表的特性，使得合并过程既直观又高效。