归并两个有序链表 将两个有序链表,合并成一个升序链表 ,把链表B的每一个节点都依次摘下来, 然后按照“插入排序”插入到链表A中
时间: 2023-06-28 07:05:28 浏览: 53
可以使用迭代的方法来归并两个有序链表:
1. 定义一个新的链表头指针 `dummy`,初始化为 `None`。
2. 定义两个指针 `p` 和 `q` 分别指向两个有序链表的头结点。
3. 遍历两个链表,比较 `p` 和 `q` 指向的节点的大小,将较小的节点插入到新链表的末尾,并将指向该节点的指针后移一位。
4. 如果其中一个链表已经遍历完,则将另一个链表的剩余部分直接插入到新链表的末尾。
5. 返回新链表的头结点 `dummy.next`。
代码实现如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode() # 新链表的头结点
cur = dummy # 新链表的当前节点
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2 # 将未遍历完的链表直接插入到新链表的末尾
return dummy.next
```
时间复杂度为 $O(m+n)$,其中 $m$ 和 $n$ 分别是两个链表的长度。
相关推荐
![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)