两个有序链表序列的合并c++完整代码
时间: 2024-10-16 16:22:12 浏览: 7
在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) {
// 初始化合并后的链表头指针为NULL
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy; // 尾部指针始终指向当前链表的最后一个元素
// 比较并逐个添加节点到新链表
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next; // 更新尾部指针
}
// 如果其中一个链表未遍历完,则将剩余部分接到新链表末尾
if (l1 != nullptr) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy->next; // 返回合并后的链表头节点
}
int main() {
// 创建示例链表
ListNode* list1 = new ListNode(1);
list1->next = new ListNode(2);
list1->next->next = new ListNode(4);
ListNode* list2 = new ListNode(1);
list2->next = new ListNode(3);
list2->next->next = new ListNode(4);
// 合并两个链表
ListNode* mergedList = mergeTwoLists(list1, list2);
// 打印合并后的链表
while (mergedList != nullptr) {
cout << mergedList->val << " ";
mergedList = mergedList->next;
}
cout << endl;
// 清理内存
delete mergedList;
return 0;
}
```
这段代码首先创建了两个示例链表`list1`和`list2`,然后通过`mergeTwoLists`函数合并它们,并返回合并后的链表。在`main`函数中,我们打印出合并后的链表值。
阅读全文