编写一个完整的程序,实现两个非递减有序排列的单链表la和lb合并为一个新的非递减有序排列的单链表lc 。
时间: 2024-09-18 12:16:50 浏览: 32
首先,让我们理解这个问题的要求:我们需要编写一个函数来合并两个已排序的链表la和lb,结果是一个新的链表lc,其中包含所有元素,按照非递增顺序排列。
下面是一个简单的Python实现示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(la, lb):
# 定义头节点和指针
dummy = ListNode(0) # 创建虚拟头节点,方便操作链表
current = dummy # 当前指针
while la and lb: # 只有当两个链表都不为空时循环
if la.val <= lb.val: # 如果la的值小于等于lb的值
current.next = la # 将la添加到新链表中
la = la.next # 移动la指针
else: # 否则
current.next = lb # 将lb添加到新链表中
lb = lb.next # 移动lb指针
current = current.next # 指针向前移动
# 如果la或lb其中一个链表还剩余未添加,则将剩余部分添加到最后
if la:
current.next = la
elif lb:
current.next = lb
return dummy.next # 返回实际的新链表头节点,即虚拟头节点的下一个节点
# 示例链表创建
la = ListNode(1)
la.next = ListNode(2)
la.next.next = ListNode(4)
lb = ListNode(1)
lb.next = ListNode(3)
lb.next.next = ListNode(4)
# 合并后的链表
lc = merge_sorted_lists(la, lb)
```
在这个例子中,`merge_sorted_lists` 函数通过比较当前节点的值,依次将较小的节点添加到新链表中。最后返回合并后的新链表。