将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
时间: 2024-08-12 07:06:49 浏览: 120
合并两个升序链表是一个常见的链表操作,可以通过迭代或递归的方式实现。基本思路是创建一个新的链表头节点,然后遍历两个输入链表,每次选择当前链表中的较小元素添加到新链表中,直到其中一个链表遍历完毕,再将另一个链表剩余的部分依次添加。
以下是合并两个升序链表的基本步骤:
1. 初始化一个新的头节点(如果链表为空,则直接返回另一个链表)
2. 创建两个指针,分别指向两个输入链表的头部
3. 比较当前节点的值,将较小的节点值添加到新链表,并移动该节点指针
4. 重复步骤3,直到其中一个链表遍历结束
5. 将另一个链表剩余部分接到新链表的尾部
下面是合并过程的伪代码示例:
```python
function merge_sorted_lists(list1_head, list2_head):
if list1_head is None:
return list2_head
if list2_head is None:
return list1_head
# 初始化新链表和指针
new_head = ListNode(None)
current = new_head
while list1_head and list2_head:
if list1_head.value <= list2_head.value:
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
```
阅读全文