合并两个有序链表c++
时间: 2023-07-04 12:28:19 浏览: 69
可以使用递归或迭代的方式实现合并两个有序链表,以下是迭代的实现方式:
```c++
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
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;
}
cur->next = l1 ? l1 : l2; // 将剩余的链表接到结果链表的尾部
return dummy->next; // 返回真实头结点
}
```
其中,虚拟头结点是为了方便链表的操作而引入的,它的值不重要,只是为了让代码更简洁。
相关问题
合并两个有序链表C++代码
合并两个有序链表是常见的链表操作,通常使用迭代或递归的方式实现。以下是使用C++的一种简单迭代方法:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 如果其中一个链表为空,直接返回另一个
if (!l1) return l2;
if (!l2) return l1;
// 定义一个新的头节点,并初始化为第一个非空链表的头
ListNode* head = (l1->val <= l2->val) ? l1 : l2;
ListNode* tail = head;
// 遍历两个链表,不断比较并选择较小的节点添加到新链表
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 将剩余的链表连接到结果链表的末尾,如果还有未遍历完的链表
if (l1) tail->next = l1; // 将l1剩余部分连接
else tail->next = l2; // 或者将l2剩余部分连接
return head;
}
```
c++合并两个有序链表 博客园
合并两个有序链表的基本思路是将两个链表按照大小顺序逐个比较,将较小的节点一个一个地插入到合并后的链表中。这个过程需要用到三个指针:一个指向合并后链表的头结点,另外两个分别指向两个原始链表的当前节点。
具体实现可以按照如下步骤:
1. 定义一个新链表的头和尾指针,初始时均指向NULL。
2. 从两个原始链表的头结点开始,比较两个节点的大小,将小的节点插入到新链表的尾部。
3. 将较小节点的指针向后移动一个单位,继续比较两个节点大小,直到其中一个链表的指针为空。
4. 将另一个链表剩余的节点直接插入到新链表的尾部。
5. 返回新链表的头指针,即为合并后的有序链表。
需要注意的是,在比较两个节点大小时,要使用它们存储的值进行比较,而非节点本身的地址。如果两个节点的值相等,则可以将任一个节点插入到新链表的尾部。
另外,为避免频繁地进行节点的插入操作,可以先比较两个节点的大小,将较小的节点存储到一个数组中,最后再将数组中的节点依次插入到新链表中。这样可以有效地提高算法的效率。
参考代码如下:
```c
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct 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;
}
```
阅读全文