有两个带附加头结点的单链表,结点包含两个域:entry和next,若单链表中的元素值递增有序排列,请写算法,将两个单链表按顺序合并成一个链表
时间: 2023-05-30 10:04:39 浏览: 105
1. 定义一个新的带附加头结点的单链表result,以及三个指针p1、p2、p,分别指向两个单链表的头结点和result的尾结点。
2. 比较p1和p2所指向结点的元素值大小,将较小的结点插入到result的尾结点后面,并将指针p指向新插入的结点。
3. 将p1或p2指向下一个结点,继续执行步骤2,直到p1或p2中的一个为空。
4. 将p指向另一个非空的单链表的剩余部分,将其插入到result的尾结点后面。
5. 返回result的头结点。
算法实现如下:
```python
def merge_sorted_lists(head1, head2):
# 定义一个新的单链表result
result = ListNode(None)
p1, p2, p = head1.next, head2.next, result
# 比较p1和p2所指向结点的元素值大小,将较小的结点插入到result的尾结点后面
while p1 and p2:
if p1.entry < p2.entry:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
# 将p指向另一个非空的单链表的剩余部分,将其插入到result的尾结点后面
p.next = p1 if p1 else p2
# 返回result的头结点
return result
```
阅读全文