已知两个长度分别为m、n(m、n均大于0)的升序单链表L1和L2,设计一个算法将它们的所有节点合并为一个长度为m+n的降序单链表L。
时间: 2024-09-29 18:13:52 浏览: 61
要合并两个升序单链表 L1 和 L2,使其成为一个降序单链表 L,你需要遍历两个链表并将较大的节点添加到新链表中。由于 L1 和 L2 都是升序的,所以从头开始比较即可得到最大值。以下是一个简单的 C++ 实现:
```cpp
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeSortedLists(ListNode* head1, ListNode* head2) {
ListNode* dummy = new ListNode(0); // 创建虚拟头结点
ListNode* tail = dummy; // 尾指针指向虚拟头
while (head1 && head2) { // 只有当两个链表都有节点时循环
if (head1->val > head2->val) {
tail->next = head1;
head1 = head1->next;
} else {
tail->next = head2;
head2 = head2->next;
}
tail = tail->next; // 更新尾指针
}
// 如果其中一个链表为空,将另一个链表剩余的部分连接到结果链表末尾
if (head1) {
tail->next = head1;
} else {
tail->next = head2;
}
return dummy->next; // 返回新的降序链表头结点
}
```
这个算法的工作原理是每次从 L1 和 L2 的头部取出一个节点,将较大的节点添加到新链表的尾部,然后移动相应的链表头指针。当其中任意一个链表遍历完后,就将其余未遍历的链表直接接到新链表的末尾。
阅读全文