合并两个有序链表是一个经典的编程问题，涉及到了数据结构和算法的运用。这个问题的目标是将两个已排序的链表（每个节点包含一个整数值）合并成一个新的有序链表。在这个任务中，我们通常假定链表的节点值是升序排列的。这里展示的是一个使用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)，仅使用了固定大小的内存来存储哑节点和指针，与链表长度无关。这个方法巧妙地利用了链表的特性，使得合并过程既直观又高效。
我的内容管理
展开
