已知单链表LA和LB的元素按值非递减排列 归并LA和LB得到新的单链表LC,LC的元素也按值非递减排列
时间: 2024-09-17 13:03:56 浏览: 130
两个非递减存储顺序线性表归并为非递减顺序线性表
要合并两个已排序的单链表LA和LB,使得合并后的链表LC按照元素值非递减顺序排列,你可以使用一种类似于归并排序的方法。这里的关键步骤包括创建一个新的头节点,然后遍历两个链表,比较当前节点的值,选择较小的那个添加到新链表中,并更新指针。
以下是一个简单的C++示例实现:
```cpp
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeSortedLists(ListNode* la, ListNode* lb) {
// 新链表的头节点
ListNode* lc = nullptr;
if (la == nullptr) return lb;
if (lb == nullptr) return la;
// 比较节点值并决定哪个添加到新链表
if (la->val <= lb->val) {
lc = la; // 如果LA较小,设置lc为LA
la = la->next;
} else {
lc = lb; // 否则,设置lc为LB
lb = lb->next;
}
// 将当前最小节点添加到新链表后,继续遍历
lc->next = mergeSortedLists(la, lb);
return lc;
}
// 打印链表
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " ";
node = node->next;
}
std::cout << std::endl;
}
int main() {
// 创建示例链表
ListNode* LA = new ListNode(1);
LA->next = new ListNode(3);
LA->next->next = new ListNode(5);
ListNode* LB = new ListNode(2);
LB->next = new ListNode(4);
LB->next->next = new ListNode(6);
// 合并并打印结果
ListNode* LC = mergeSortedLists(LA, LB);
printList(LC);
return 0;
}
```
当你运行这段代码时,输出将是`1 2 3 4 5 6`,这是按照值非递减顺序排列的新链表LC。
阅读全文