链表操作:合并两个带有头结点的有序单链表 void Merge(MList& another); 默认当前链表和another链表中存储的数据都是从小到到大的, 并且将 another链表的中结点合并到当前链表中,不要开辟新的结点空间。 利用c++语言实现
时间: 2024-09-28 13:07:23 浏览: 37
在C++中,合并两个有序的单链表(MList),不需要额外的空间,可以利用迭代的方式逐个比较节点的值,将较大的节点添加到当前链表中。以下是这个操作的实现:
```cpp
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 自定义链表类
class MList {
public:
ListNode* head;
// 合并函数
void Merge(MList& another) {
ListNode dummy(0); // 创建一个虚拟头节点
ListNode* tail = &dummy; // 初始化tail为虚拟头节点
// 遍历另一个链表,将较大的节点添加到当前链表
while (head && another.head) {
if (head->val <= another.head->val) {
tail->next = head;
head = head->next;
} else {
tail->next = another.head;
another.head = another.head->next;
}
tail = tail->next;
}
// 添加另一个链表剩余部分(如果有的话)
if (another.head)
tail->next = another.head;
}
};
// 示例如何使用
int main() {
MList list1, list2; // 初始化两个链表...
// ...填充链表...
list1.Merge(list2); // 合并两个链表
// 打印合并后的链表
ListNode* curr = list1.head;
while (curr != nullptr) {
std::cout << curr->val << " -> ";
curr = curr->next;
}
std::cout << "nullptr" << std::endl;
return 0;
}
```
在这个实现中,我们首先创建一个虚拟头节点`dummy`,并初始化`tail`为`dummy`。然后在两个链表非空的情况下,比较当前节点的值,将较大的节点添加到`tail`的下一个位置,并更新`head`或`another.head`。最后,处理可能存在的另一个链表剩余部分。
阅读全文