请用c++语言写一个完成的程序
时间: 2023-10-06 14:08:10 浏览: 32
好的,以下是用 C++ 语言实现的完整程序:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x): val(x), next(nullptr) {}
};
ListNode* mergeSort(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = nullptr;
ListNode* left = mergeSort(head);
ListNode* right = mergeSort(mid);
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (left && right) {
if (left->val <= right->val) {
cur->next = left;
left = left->next;
} else {
cur->next = right;
right = right->next;
}
cur = cur->next;
}
cur->next = left ? left : right;
return dummy->next;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
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;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
int main() {
int n1, n2;
cin >> n1;
vector<int> vals1(n1);
for (int i = 0; i < n1; i++) {
cin >> vals1[i];
}
cin >> n2;
vector<int> vals2(n2);
for (int i = 0; i < n2; i++) {
cin >> vals2[i];
}
ListNode* head1 = new ListNode(-1);
ListNode* tail1 = head1;
for (int val : vals1) {
tail1->next = new ListNode(val);
tail1 = tail1->next;
}
head1 = head1->next;
ListNode* head2 = new ListNode(-1);
ListNode* tail2 = head2;
for (int val : vals2) {
tail2->next = new ListNode(val);
tail2 = tail2->next;
}
head2 = head2->next;
ListNode* sortedHead1 = mergeSort(head1);
ListNode* sortedHead2 = mergeSort(head2);
ListNode* mergedHead = mergeTwoLists(sortedHead1, sortedHead2);
while (mergedHead) {
cout << mergedHead->val << " ";
mergedHead = mergedHead->next;
}
return 0;
}
```
输入示例:
```
2
1 2
3
1 2 3
```
输出示例:
```
1 1 2 2 3
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)