用尾部插入法创建两个元素有序的单链表,然后合并这两个单链表,并保持有序
时间: 2024-09-28 18:17:32 浏览: 46
尾部插入法合并两个有序链表的过程可以分为以下几个步骤:
1. 创建一个新的头结点,这个头结点用于最终的结果链表。
2. 初始化三个指针,分别指向第一个待合并链表的头、第二个链表的头以及新链表的头节点。
3. 比较两个链表当前节点的值,将较小的值所在的节点插入到新链表的尾部,并移动相应的指针。如果其中一个链表已空,直接将另一个链表剩余部分添加到新链表即可。
4. 重复步骤3,直到两个链表都有一个为空。
以下是伪代码形式的示例:
```python
def merge_sorted_lists(list1_head, list2_head):
if not list1_head or not list2_head:
return list1_head if list1_head else list2_head
# 新链表的头节点
new_head = ListNode(0)
current = new_head
while list1_head and list2_head:
if list1_head.val < list2_head.val:
current.next = list1_head
list1_head = list1_head.next
else:
current.next = list2_head
list2_head = list2_head.next
current = current.next
# 如果有一个链表未遍历完,则将其剩余部分追加到新链表
if list1_head:
current.next = list1_head
else:
current.next = list2_head
return new_head.next
```
阅读全文