已知两个非递减有序单链表La与Lb,编写程序把La和Lb合并为新的非递减有序链表Lc。
时间: 2024-12-20 07:24:42 浏览: 22
将两个非递减有序的单链表La和Lb合并成一个新的非递减有序链表Lc,可以采用迭代或者递归的方式。这里我们提供一种相对简单的迭代方法:
1. 创建一个新的链表节点`newHead`作为合并后的链表头。
2. 初始化两个指针`p1`和`p2`分别指向La和Lb的头部。
3. 比较两个链表当前节点的值,将较小的节点添加到新链表中,并将其指向的下一个节点设为当前节点,然后移动相应的指针。
4. 如果其中一个链表遍历完了,就将另一个链表剩余的部分接到新链表的尾部。
伪代码示例:
```python
def merge_sorted_lists(la_head, lb_head):
new_head = ListNode(0) # 新链表的头节点
current = new_head
while la_head and lb_head:
if la_head.val <= lb_head.val:
current.next = la_head
la_head = la_head.next
else:
current.next = lb_head
lb_head = lb_head.next
current = current.next
# 将未遍历完的链表添加到新链表尾部
if la_head:
current.next = la_head
elif lb_head:
current.next = lb_head
return new_head.next # 返回合并后的链表头节点
```
阅读全文