将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
时间: 2023-04-20 21:01:44 浏览: 64
请给出代码实现:
```
/**
* 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) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
```
相关问题
将两个升序链表合并为一个新的升序链表,新链表时通过拼接给定的两个链表的所有节点组成
可以使用递归的方式来解决这个问题。首先比较两个链表的头节点,将较小的节点作为新链表的头节点,然后递归地合并剩余的节点。
下面是一个示例的C++代码实现:
```cpp
#include <iostream>
using namespace std;
// 链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 合并两个升序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 如果其中一个链表为空,则直接返回另一个链表
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
// 比较两个链表的头节点,将较小的节点作为新链表的头节点
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
// 打印链表
void printList(ListNode* head) {
ListNode* curr = head;
while (curr != NULL) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
}
int main() {
// 创建两个有序链表
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(3);
l1->next->next = new ListNode(5);
ListNode* l2 = new ListNode(2);
l2->next = new ListNode(4);
l2->next->next = new ListNode(6);
// 合并两个链表
ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
```
输出结果为:1 2 3 4 5 6,表示成功将两个升序链表合并为一个新的升序链表。
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
可以使用双指针法,分别指向两个链表的头结点,比较两个指针所指节点的大小,将较小的节点加入新链表中,并将指针后移。直到其中一个链表为空,将另一个链表剩余的节点加入新链表中即可。最后返回新链表的头结点即可。