在Python中合并两个有序链表应该使用什么方法?
时间: 2024-09-10 12:30:38 浏览: 45
在Python中,合并两个有序链表通常会使用迭代的方法来实现。这涉及到创建一个新的链表节点,然后按顺序比较两个链表的节点值,依次选择较小的节点添加到新链表中,直到其中一个链表遍历完成。如果一个链表遍历完毕而另一个还有剩余节点,则将剩余部分直接连接到新链表的末尾。这个过程使用的是“归并排序”中的合并步骤。
以下是一个合并两个有序链表的Python函数示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
# 创建一个哨兵节点,它将作为合并后链表的头部
sentinel = ListNode(0)
current = sentinel
# 当两个链表都不为空时,进行比较
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
# 如果l1还有剩余节点,直接连接到新链表的末尾
if l1:
current.next = l1
# 如果l2还有剩余节点,直接连接到新链表的末尾
elif l2:
current.next = l2
# 返回合并后链表的头节点
return sentinel.next
```
在这个示例中,`ListNode`类用于表示链表节点,`mergeTwoLists`函数用于合并两个有序链表。这个函数首先创建了一个哨兵节点来简化边界条件的处理,然后通过比较两个链表的节点值来构建新的有序链表。
阅读全文