c++将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来 两个链表的存储空间, 不另外占用其它的存储空间。
时间: 2024-03-25 11:34:52 浏览: 80
设计算法合并非递减有序链表
5星 · 资源好评率100%
要将两个非递减的有序链表合并为一个非递增的有序链表,并且要求结果链表仍使用原来两个链表的存储空间,可以按照以下步骤进行操作:
1. 创建一个新的指针`result`,指向两个链表中较小的头节点。
2. 创建两个指针`p1`和`p2`,分别指向两个链表的当前节点。
3. 遍历两个链表,比较`p1`和`p2`指向节点的值,将较小的节点连接到`result`指向的链表上,并更新相应的指针。
4. 如果其中一个链表遍历完了,将另一个链表剩余的部分直接连接到`result`指向的链表上。
5. 最后,将原来两个链表的头节点指向`result`指向的链表。
下面是C++代码实现:
```cpp
void mergeLinkedList(ListNode* l1, ListNode* l2) {
if (l1 == nullptr || l2 == nullptr) {
return;
}
ListNode* result = (l1->val <= l2->val) ? l1 : l2;
ListNode* p1 = result;
ListNode* p2 = (p1 == l1) ? l2 : l1;
while (p1->next != nullptr && p2 != nullptr) {
if (p1->next->val <= p2->val) {
p1 = p1->next;
} else {
ListNode* temp = p1->next;
p1->next = p2;
p2 = temp;
}
}
if (p1->next == nullptr) {
p1->next = p2;
}
l1 = result;
}
```
阅读全文