已知两个非递减有序单链表La与Lb,编写程序把La和Lb合并为新的非递减有序链表Lc
时间: 2024-10-29 16:18:19 浏览: 34
设计算法合并非递减有序链表
5星 · 资源好评率100%
要合并两个已排序的非递减单链表La和Lb,创建一个新的链表Lc,可以采用双指针法。以下是算法步骤:
1. 初始化三个指针:p1指向La的头节点,p2指向Lb的头节点,以及新链表Lc的头节点head为None(空)。
2. 当p1或p2有一个变为None时,将另一个链表剩余部分接到Lc的末尾。
3. 比较p1和p2的值,将较小的那个节点添加到Lc,并将其指针更新为其下一个节点。如果它们相等,可以选择任意一个(为了保持链表顺序一致性),并将另一个移动到下一个节点。
4. 重复步骤3,直到其中一个指针遍历完其链表。
5. 将最后一个遍历完的链表的剩余部分连接到Lc的末尾。
以下是Python伪代码实现:
```python
def merge_sorted_lists(la_head, lb_head):
p1 = la_head
p2 = lb_head
head = None
current = None
while p1 is not None and p2 is not None:
if p1.value <= p2.value:
if head is None:
head = current = ListNode(p1.value)
else:
current.next = ListNode(p1.value)
current = current.next
p1 = p1.next
else:
if head is None:
head = current = ListNode(p2.value)
else:
current.next = ListNode(p2.value)
current = current.next
p2 = p2.next
# 如果有一个链表未遍历完,将其余部分接到Lc
if p1 is not None:
current.next = p1
elif p2 is not None:
current.next = p2
return head
```
其中`ListNode`是一个假设存在的链表节点类,包含`value`属性和`next`引用。
阅读全文