根据数据结构,用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-25 19:14:46 浏览: 50
在C++中,你可以通过迭代的方式解决这个问题。首先,创建一个虚拟头节点作为临时指针,然后遍历两个链表,每次比较当前节点的值,选择较小的那个插入到结果链表中,并移动指向较小节点的指针。如果其中一个链表遍历完,就把另一个链表剩余的部分直接添加到结果链表。以下是简单的C++代码实现:
```cpp
#include <iostream>
// 定义链表节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* LA, ListNode* LB) {
// 创建虚拟头节点
ListNode dummy(0);
ListNode* tail = &dummy;
// 比较并合并两个链表
while (LA && LB) {
if (LA->val <= LB->val) {
tail->next = LA;
LA = LA->next;
} else {
tail->next = LB;
LB = LB->next;
}
tail = tail->next;
}
// 如果有一个链表未遍历完,直接添加
if (LA)
tail->next = LA;
else
tail->next = LB;
return dummy.next; // 返回实际链表的头节点
}
// 测试函数
void printList(ListNode* head) {
while (head != NULL) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << "\n";
}
int main() {
// 创建示例链表
ListNode* LA = new ListNode(2);
LA->next = new ListNode(4);
LA->next->next = new ListNode(4);
LA->next->next->next = new ListNode(6);
ListNode* LB = new ListNode(1);
LB->next = new ListNode(3);
LB->next->next = new ListNode(3);
LB->next->next->next = new ListNode(5);
ListNode* LC = mergeTwoLists(LA, LB);
printList(LC); // 输出合并后的链表
return 0;
}
```
当你运行这个程序,它会输出`1 2 3 3 4 4 5 6`,这正是题目所描述的合并后的链表。
阅读全文