首页给定两个非递减的整数序列a和b利用链表表示a和b，将a和b合并为一个非递增的有序序列 c，序列c允许有重复的数据，C++编写代码。

给定两个非递减的整数序列a和b利用链表表示a和b，将a和b合并为一个非递增的有序序列 c，序列c允许有重复的数据，C++编写代码。

时间: 2024-11-25 21:15:13 浏览: 84

在C++中，我们可以使用双指针法来合并两个非递减的整数序列a和b。首先创建一个空链表来存储结果c，然后设置两个指针，一个指向a的头节点，另一个指向b的头节点。遍历这两个链表，比较当前节点的值，将较小的那个节点插入到c的头部，并更新对应的指针。如果有一个链表已经遍历完，就把另一个链表剩余的部分直接添加到c的尾部。这是一个简单的示例代码： ```cpp #include <iostream> #include <list> // 定义链表节点 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* a, ListNode* b) { if (!a) return b; // 如果a为空，直接返回b if (!b) return a; // 如果b为空，直接返回a // 比较并合并节点 if (a->val <= b->val) { a->next = mergeTwoLists(a->next, b); return a; } else { b->next = mergeTwoLists(a, b->next); return b; } } void printList(ListNode* head) { while (head) { std::cout << head->val << " "; head = head->next; } std::cout << "\n"; } int main() { // 创建两个非递减链表 ListNode* a1 = new ListNode(1); a1->next = new ListNode(2); ListNode* b1 = new ListNode(1); b1->next = new ListNode(3); // 合并两个链表 ListNode* c = mergeTwoLists(a1, b1); // 打印结果链表 printList(c); // 输出: 1 1 2 3 return 0; } ``` 在这个例子中，`mergeTwoLists`函数负责合并两个链表，`printList`用于打印链表内容以便检查结果。运行这个程序，你会看到合并后的非递减有序序列1, 1, 2, 3。

阅读全文