C++两个不带表头结点链表合并成一个新链表 为递减有序链表并让原链表为空
时间: 2024-09-25 11:03:36 浏览: 10
在C++中,合并两个不带头节点的递增有序链表,并将其变为递减有序链表,可以按照以下步骤操作:
1. 创建一个新的链表作为结果,初始化它为空;
2. 遍历两个输入链表,分别设置当前节点为各自链表的头节点;
3. 比较两个当前节点的值,将较小的那个节点添加到结果链表的尾部,并将其指针更新为下一个较小值的节点;
4. 如果某个链表遍历完还没结束,则将另一个链表剩余部分直接添加到结果链表的尾部。
下面是伪代码形式的示例:
```cpp
Node* mergeSortedLists(Node* list1, Node* list2) {
// 新链表头部
Node* result = nullptr;
// 当前指针指向两个链表的最小节点
Node* current1 = list1;
Node* current2 = list2;
while (current1 && current2) {
if (current1->value > current2->value) {
// 将list2的节点添加到result后并移动指针
result->next = current2;
result = current2;
current2 = current2->next;
} else {
// 同理,将list1的节点添加到result后并移动指针
result->next = current1;
result = current1;
current1 = current1->next;
}
}
// 将未遍历完的部分添加到结果链表尾部
if (current1)
result->next = current1;
else
result->next = current2;
// 返回新的头节点
return result;
}