利用c++,有两个单链表LA和LB,其元素均为递增有序序列,将它们合并成一个单链表LC,要求LC也是递增有序序列,且不增加新结点。 如LA=(2,4,4,6),LB=(1,3,3,5),则LC=(1,2,3,3,4,4,5,6)。
时间: 2024-10-27 07:11:06 浏览: 16
2_链表_求la和lb的交集_
5星 · 资源好评率100%
在C++中,合并两个递增有序的单链表LA和LB,可以采用迭代或递归的方式,同时利用头插法(即在每个节点的前面插入元素)保持链表的有序性,而不需要创建新的节点。这里提供一种迭代的解决方案:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* la, ListNode* lb) {
if (!la) return lb;
if (!lb) return la;
// 如果LA的当前节点值小于LB,将LA的节点插入到结果链表中
if (la->val < lb->val) {
la->next = mergeTwoLists(la->next, lb);
return la;
} else { // 否则,将LB的节点插入到结果链表中
lb->next = mergeTwoLists(la, lb->next);
return lb;
}
}
```
这个函数会遍历两个链表,每当遇到LA的节点值小于下一个LB的节点时,就将LA的节点移到结果链表,并继续比较;反之,将LB的节点移到结果链表。最终返回的结果就是合并后的有序链表LC。
阅读全文