用C++创建两个链表,将两个有序表合并为一个有序表。
时间: 2024-02-21 20:59:14 浏览: 66
c++ 如何合并两个有序链表
5星 · 资源好评率100%
好的,这是一个比较基础的链表问题。以下是一个示例代码,供您参考:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(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;
} else {
cur->next = l2;
}
return dummy->next;
}
int main() {
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(3);
l1->next->next = new ListNode(5);
ListNode* l2 = new ListNode(2);
l2->next = new ListNode(4);
l2->next->next = new ListNode(6);
ListNode* merged = mergeTwoLists(l1, l2);
while (merged) {
cout << merged->val << " ";
merged = merged->next;
}
return 0;
}
```
以上代码使用了类似归并排序的方式,遍历两个链表,将较小的节点接到新的链表上。最后将剩余的节点接入新链表即可。
阅读全文