请写一个c++方法,使两链表合并为一个链表
时间: 2024-11-22 10:44:14 浏览: 3
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
在C++中,你可以编写一个函数`mergeTwoLists`来合并两个已排序的单链表。这里是一个简单的递归方法:
```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 == nullptr) return l2;
if (l2 == nullptr) 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* node) {
while (node != nullptr) {
cout << node->val << " -> ";
node = node->next;
}
cout << "nullptr" << endl;
}
int main() {
// 示例:合并两个已排序的链表 [1, 2, 4] 和 [1, 3, 4]
ListNode* l1 = new ListNode{1};
l1->next = new ListNode{2};
l1->next->next = new ListNode{4};
ListNode* l2 = new ListNode{1};
l2->next = new ListNode{3};
l2->next->next = new ListNode{4};
ListNode* merged = mergeTwoLists(l1, l2);
printList(merged); // 输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> nullptr
return 0;
}
```
这个函数首先检查两个链表是否为空,然后递归地比较并连接两个链表的头部,直到其中一个链表为空为止。
阅读全文