数据结构中用c++完成将两个单链表合并成一个单链表的代码
时间: 2024-10-27 11:11:09 浏览: 6
在 C++ 中,合并两个单链表通常涉及到创建一个新的节点,并通过遍历两个链表,逐个比较节点的值,将较小的节点添加到新链表中。这里是一个简单的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 创建头节点指针
ListNode* head = nullptr;
ListNode* tail = nullptr;
// 遍历两个链表
while (l1 != nullptr && l2 != nullptr) {
// 如果l1节点的值小于l2节点,添加l1;否则添加l2
if (l1->val < l2->val) {
if (head == nullptr) {
head = tail = l1;
} else {
tail->next = l1;
tail = l1;
}
l1 = l1->next;
} else {
if (head == nullptr) {
head = tail = l2;
} else {
tail->next = l2;
tail = l2;
}
l2 = l2->next;
}
}
// 将剩余未处理的部分链接至结果链表
if (l1 != nullptr) {
tail->next = l1;
} else {
tail->next = l2;
}
return head;
}
// 测试函数
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 << "nullptr" << endl;
return 0;
}
```
这个代码首先检查两个链表是否为空,然后通过while循环比较并添加节点,直到其中一个链表遍历完。最后返回合并后的链表头部。
阅读全文