python编程 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
时间: 2023-10-19 11:05:09 浏览: 37
以下是Python的代码实现:
```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(0)
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
```
注释中已经解释了每一步的操作,这里就不再赘述。
相关问题
将两个升序链表合并为一个新的升序链表并返回
题目描述:
将两个升序链表合并为一个新的升序链表并返回。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解题思路:
使用双指针法,将两个链表中的节点逐一比较,将较小的节点加入到新的链表中,直到其中一个链表为空,再将另一个链表中剩余的节点加入到新的链表中。
代码实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(); // 新链表的虚拟头节点
ListNode* cur = dummy; // 新链表的当前节点
while (l1 && l2) { // 两个链表都不为空时
if (l1->val < l2->val) { // l1的节点值小于l2的节点值
cur->next = l1; // 将l1的节点加入到新链表中
l1 = l1->next; // l1指针后移
} else { // l2的节点值小于等于l1的节点值
cur->next = l2; // 将l2的节点加入到新链表中
l2 = l2->next; // l2指针后移
}
cur = cur->next; // 新链表的当前节点后移
}
cur->next = l1 ? l1 : l2; // 将剩余的节点加入到新链表中
return dummy->next; // 返回新链表的头节点
}
};
将两个升序链表合并为一个新的升序链表并输出
以下是Python实现将两个升序链表合并为一个新的升序链表的方法:
```python
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# 如果其中一个链表为空,则直接返回另一个链表
if not l1:
return l2
if not l2:
return l1
# 定义一个新链表的头节点
dummy = ListNode(0)
# 定义一个指针指向新链表的头节点
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
# 将剩余的节点加入新链表中
if l1:
cur.next = l1
if l2:
cur.next = l2
# 返回新链表的头节点
return dummy.next
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)