根据数据结构,用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 10:14:46 浏览: 37
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
在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`,这正是题目所描述的合并后的链表。
阅读全文