有两个递增有序的单链表la和lb。设计算法将这两个链表合并为一个有序链表的代码。
时间: 2024-10-05 21:00:32 浏览: 39
要合并两个递增有序的单链表la和lb,你可以采用分治策略,创建一个新的链表并维护当前指向新链表的指针current。遍历两个链表,每次比较当前节点的值,将较小的那个添加到新链表,并更新指针。
以下是Python语言的一个简单示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(la, lb):
# 创建头节点和空链表作为结果
dummy_head = ListNode(0)
current = dummy_head
while la and lb:
if la.val < lb.val:
current.next = la
la = la.next
else:
current.next = lb
lb = lb.next
current = current.next
# 如果其中一个链表还有剩余元素,则追加到结果链表末尾
if la:
current.next = la
elif lb:
current.next = lb
return dummy_head.next
# 使用示例:
la = ListNode(1, ListNode(2, ListNode(4)))
lb = ListNode(1, ListNode(3, ListNode(5)))
merged_list = merge_sorted_lists(la, lb)
```
这个函数会返回一个新的链表,其中包含了原两个链表的所有元素,按照升序排列。如果你想了解如何在其他编程语言中实现,只需相应地调整数据结构和循环条件即可。
阅读全文