合并两个有序链表cpp
时间: 2023-09-02 21:11:36 浏览: 53
可以通过迭代或递归的方式合并两个有序链表。以下是迭代的实现方法:
```cpp
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
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;
}
```
首先建立一个虚拟头结点 dummy,然后定义一个指针 cur 指向 dummy。然后遍历两个链表,比较当前两个链表头结点的大小,将较小的那个加入到合并后的链表中,并将指针 cur 指向它。最后将没遍历完的链表直接接在合并后的链表尾部即可。
这里假设两个链表已经按照升序排列。
相关问题
cpp 合并两个有序链表
可以通过递归或迭代的方式实现合并两个有序链表。以下是迭代实现的示例代码:
```cpp
#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(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
int main() {
ListNode a(1);
ListNode b(2);
ListNode c(4);
a.next = &b;
b.next = &c;
ListNode d(1);
ListNode e(3);
ListNode f(4);
d.next = &e;
e.next = &f;
ListNode* merged = mergeTwoLists(&a, &d);
while (merged) {
cout << merged->val << " ";
merged = merged->next;
}
cout << endl;
return 0;
}
```
在上面的代码中,我们创建了一个 dummy 节点作为合并后链表的头节点,使用 tail 指针指向当前已经合并的节点的末尾。然后,我们不断比较 l1 和 l2 的当前节点的值,将较小值的节点接到 tail 后面,同时将该链表的指针向后移动一位。最后,将剩余的链表接到 tail 后面即可。
用VS写一个完整的合并两个有序链表程序,并且逐行注释
好的,以下是使用 VS 编写的完整的合并两个有序链表程序,逐行注释:
```cpp
#include <iostream>
using namespace std;
// 定义链表结点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {} // 构造函数
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2; // 如果 l1 为空,直接返回 l2
if (!l2) return l1; // 如果 l2 为空,直接返回 l1
ListNode* dummy = new ListNode(0); // 创建虚拟头结点
ListNode* cur = dummy; // 当前结点
// 遍历两个链表,直到其中一个链表为空
while (l1 && l2) {
if (l1->val <= l2->val) { // 如果 l1 的值小于等于 l2 的值
cur->next = l1; // 将 l1 的结点接到结果链表的尾部
l1 = l1->next; // l1 向后移动一位
} else { // 如果 l2 的值小于等于 l1 的值
cur->next = l2; // 将 l2 的结点接到结果链表的尾部
l2 = l2->next; // l2 向后移动一位
}
cur = cur->next; // 当前结点向后移动一位
}
cur->next = l1 ? l1 : l2; // 将剩余的链表接到结果链表的尾部
return dummy->next; // 返回真实头结点
}
// 输出链表
void printList(ListNode* head) {
ListNode* cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
int main() {
// 创建两个有序链表
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(2);
l1->next->next = new ListNode(4);
ListNode* l2 = new ListNode(1);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);
// 输出原始链表
cout << "l1: ";
printList(l1);
cout << "l2: ";
printList(l2);
// 合并两个有序链表
ListNode* mergedList = mergeTwoLists(l1, l2);
// 输出合并后的链表
cout << "merged list: ";
printList(mergedList);
return 0;
}
```
这个程序首先定义了一个 `ListNode` 结构体,用于表示链表的结点。然后,`mergeTwoLists` 函数用于合并两个有序链表,返回合并后的链表的头结点。最后,`printList` 函数用于输出一个链表。
在 `main` 函数中,首先创建了两个有序链表 `l1` 和 `l2`,并输出它们的值。然后,调用 `mergeTwoLists` 函数合并这两个链表,并输出合并后的链表。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.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)