c++单链表merge
时间: 2024-09-19 18:13:22 浏览: 23
在 C++ 中,合并两个已排序的单链表通常是通过递归或迭代的方式来实现的,这叫做合并排序链表。这里我会给你一个简单的迭代方法:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 创建一个新的头节点作为结果
ListNode* result = nullptr;
// 定义三个指针,分别指向两个列表和结果列表的当前位置
ListNode* p1 = l1, *p2 = l2, *prev_result = result;
// 当任一链表非空时继续比较
while (p1 != nullptr && p2 != nullptr) {
if (p1->val < p2->val) {
// 如果l1的元素较小,将其添加到结果并移动p1
prev_result->next = p1;
prev_result = p1;
p1 = p1->next;
} else {
// 否则,将l2的元素添加到结果并移动p2
prev_result->next = p2;
prev_result = p2;
p2 = p2->next;
}
}
// 将剩余未处理的部分添加到结果链表
if (p1 != nullptr) {
prev_result->next = p1;
} else {
prev_result->next = p2;
}
return result; // 返回新的合并后的链表头部
}
```