合并两个带有头结点的有序单链表 void Merge(MList& another); 默认当前链表和another链表中存储的数据都是从小到到大的, 并且将 another链表的中结点合并到当前链表中,不要开辟新的结点空间。 利用c++语言
时间: 2024-09-28 19:07:43 浏览: 50
在C++中,合并两个已排序的单链表(MList)而不需要额外的空间,可以采用“归并”算法的思想。这里假设`Merge()`函数接收的是一个引用参数`another`,并且链表节点包含一个整数值以及指向下一个节点的指针。以下是合并操作的一个示例实现:
```cpp
class MListNode {
public:
int val;
MListNode* next;
// 构造函数和其他必要的成员函数...
};
void Merge(MList& current, const MList& another) {
if (current.head == nullptr) { // 如果当前链表为空
current.head = another.head;
} else if (another.head != nullptr && another.head->val < current.head->val) { // another链表非空且值小
current.head->next = another.head;
another.head = another.head->next;
} else { // another链表非空且值大或相等,开始遍历另一个链表
MListNode* temp = current.head;
while (temp->next != nullptr && another.head != nullptr) {
if (another.head->val <= temp->next->val) { // another节点值小于等于temp.next节点值
temp->next = another.head;
another.head = another.head->next;
} else { // 另一个节点值大于temp.next节点值,继续移动temp
temp = temp->next;
}
}
if (another.head != nullptr) { // another链表剩余部分追加到当前链表尾部
temp->next = another.head;
}
}
}
```
这个函数会修改`current`链表,使得其按照升序排列。注意,此实现假设`another`链表也已排序,并且在比较节点值时直接使用了 `<` 操作符。
阅读全文