能否提供一个Python代码示例,展示如何将两个已排序的链表合并成一个新的有序链表?
时间: 2024-10-25 08:03:24 浏览: 39
当然可以。在Python中,我们可以创建一个`ListNode`类表示链表节点,并实现一个函数`merge_sorted_lists`来合并两个已排序的链表。这里是一个简单的例子:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
if not l1:
return l2
elif not l2:
return l1
else:
# 如果l1小于l2,则l1作为新链表的头,否则反之
if l1.val < l2.val:
l1.next = merge_sorted_lists(l1.next, l2)
return l1
else:
l2.next = merge_sorted_lists(l1, l2.next)
return l2
# 示例:假设我们有两个链表 l1 = [1, 4, 5] 和 l2 = [1, 3, 4]
l1 = ListNode(1, ListNode(4, ListNode(5)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
merged_list = merge_sorted_lists(l1, l2)
while merged_list:
print(merged_list.val, end=" -> ")
merged_list = merged_list.next
```
这个函数会返回一个新的链表,其中包含了输入链表l1和l2的所有元素,按照升序排列。
阅读全文