题目描述:输出两个单向有序链表的并集 如链表 A {1 -> 2 -> 5 -> 7} 链表 B {3 -> 5 -> 7 -> 8} 输出: {1 -> 2 ->3 -> 5 -> 7 ->8} 。输入描述:第一行输入整数n,m,(1<=n,m<=1000)分别表示两个链表的长度。 第二行给出A链表所包含元素。(1<=a<=1000) 第三行给出B链表所包含元素。(1<=b<=1000)
时间: 2024-03-20 08:43:46 浏览: 18
好的,我会尽力回答你的问题。这个问题可以使用双指针来解决。我们可以设置两个指针分别指向两个链表的头节点,比较两个节点的值的大小,将小的节点加入到新的链表中,并将对应的指针向后移动一位,直到其中一个链表为空。然后将另一个链表中剩余的节点加入到新的链表中。最后返回新的链表即可。以下是 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeList(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0); // 新建一个虚拟头节点
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1; // 将剩余的节点加入到新链表中
if (l2) cur->next = l2;
return dummy->next;
}
int main() {
int n, m;
cin >> n >> m;
ListNode* l1 = new ListNode(0);
ListNode* l2 = new ListNode(0);
ListNode* p1 = l1;
ListNode* p2 = l2;
int num;
for (int i = 0; i < n; i++) {
cin >> num;
p1->next = new ListNode(num);
p1 = p1->next;
}
for (int i = 0; i < m; i++) {
cin >> num;
p2->next = new ListNode(num);
p2 = p2->next;
}
ListNode* res = mergeList(l1->next, l2->next);
while (res) {
cout << res->val << " ";
res = res->next;
}
return 0;
}
```
希望能帮到你!