使用python有两个带附加头结点的单链表,结点包含两个域:entry和next,若单链表中的元素值递增有序排列,请写算法,将两个单链表按顺序合并成一个链表。
时间: 2023-05-30 13:03:49 浏览: 104
python算法与数据结构之单链表的实现代码
可以使用双指针合并两个有序单链表,具体步骤如下:
1. 创建一个新的头结点new_head,并将其next指向None。
2. 定义两个指针p和q,分别指向两个单链表的第一个节点。
3. 比较p和q节点的entry值大小,将entry值小的节点插入到new_head链表的末尾,并将指针p或q向后移动一个节点。
4. 重复步骤3,直到p或q指向None。
5. 如果p或q还有剩余节点,则将剩余节点插入到new_head链表的末尾。
6. 返回new_head链表的头结点。
下面是Python代码实现:
```python
class Node:
def __init__(self, entry=None, next=None):
self.entry = entry
self.next = next
def merge_sorted_lists(head1, head2):
new_head = Node()
p = head1.next
q = head2.next
tail = new_head
while p and q:
if p.entry <= q.entry:
tail.next = p
p = p.next
else:
tail.next = q
q = q.next
tail = tail.next
if p:
tail.next = p
if q:
tail.next = q
return new_head
```
其中,head1和head2分别为两个带附加头结点的有序单链表的头结点。调用merge_sorted_lists函数即可得到合并后的有序单链表的头结点。
阅读全文