Python 有两个带附加头结点的单链表,结点包含两个域:entry和next,若单链表中的元素值递增有序排列,请写算法,将两个单链表按顺序合并成一个链表。
时间: 2023-05-30 11:05:05 浏览: 124
算法步骤如下:
1. 创建一个新的头结点head,以及一个游标指针p指向head。
2. 比较两个链表当前节点的值,将值较小的节点加入到新链表中,并将游标指针p指向新加入的节点。
3. 继续比较两个链表的下一个节点,重复步骤2,直到其中一个链表全部加入到新链表中。
4. 将另一个链表中剩余的节点加入到新链表中。
5. 返回新链表的头结点head。
代码如下:
```python
def merge_lists(head1, head2):
# 创建一个新的头结点head,以及一个游标指针p指向head
head = ListNode(None)
p = head
# 比较两个链表当前节点的值,将值较小的节点加入到新链表中,并将游标指针p指向新加入的节点
while head1 and head2:
if head1.entry < head2.entry:
p.next = head1
head1 = head1.next
else:
p.next = head2
head2 = head2.next
p = p.next
# 将另一个链表中剩余的节点加入到新链表中
if head1:
p.next = head1
if head2:
p.next = head2
# 返回新链表的头结点head
return head.next
```
阅读全文