对两个递增的单链表进行二路归并
时间: 2024-06-15 13:04:44 浏览: 10
对两个递增的单链表进行二路归并是一种常见的链表操作,可以将两个有序链表合并成一个有序链表。下面是一种实现方式:
1. 创建一个新的链表作为结果链表的头节点,并用一个指针指向它。
2. 比较两个链表的当前节点的值,将较小的节点添加到结果链表中,并将指针指向下一个节点。
3. 重复步骤2,直到其中一个链表遍历完毕。
4. 将剩余未遍历完的链表直接连接到结果链表的末尾。
5. 返回结果链表的头节点。
以下是示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0) # 创建结果链表的头节点
curr = dummy # 指针指向结果链表的头节点
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# 将剩余未遍历完的链表直接连接到结果链表的末尾
if l1:
curr.next = l1
if l2:
curr.next = l2
return dummy.next # 返回结果链表的头节点
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)