首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

合并两个链表算法分割故障C++

合并两个链表算法是指将两个有序链表合并为一个新的有序链表的算法。这个算法可以用于合并两个有序链表,使得合并后的链表仍然保持有序。

C++代码示例:

代码语言:txt
复制
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
        return l2;
    }
    if (l2 == nullptr) {
        return l1;
    }
    
    ListNode* dummy = new ListNode(0);
    ListNode* curr = dummy;
    
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    
    if (l1 != nullptr) {
        curr->next = l1;
    }
    if (l2 != nullptr) {
        curr->next = l2;
    }
    
    ListNode* result = dummy->next;
    delete dummy;
    
    return result;
}

int main() {
    // 创建链表1: 1 -> 2 -> 4
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);
    
    // 创建链表2: 1 -> 3 -> 4
    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);
    
    // 合并两个链表
    ListNode* mergedList = mergeTwoLists(l1, l2);
    
    // 输出合并后的链表: 1 -> 1 -> 2 -> 3 -> 4 -> 4
    ListNode* curr = mergedList;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    
    // 释放内存
    delete l1;
    delete l2;
    delete mergedList;
    
    return 0;
}

该算法的时间复杂度为O(n+m),其中n和m分别是两个链表的长度。算法通过比较两个链表的节点值,依次选择较小的节点连接到新的链表中,直到其中一个链表遍历完毕。最后,将剩余的节点直接连接到新链表的末尾。

这个算法在实际开发中常用于合并有序链表,例如合并两个有序的用户列表、合并两个有序的日志文件等场景。

腾讯云相关产品推荐:

  • 云服务器(CVM):提供弹性计算能力,满足各类业务需求。产品介绍
  • 云数据库MySQL版(CDB):提供高可用、可扩展的关系型数据库服务。产品介绍
  • 云原生容器服务(TKE):基于Kubernetes的容器管理服务,简化容器化应用的部署和管理。产品介绍
  • 人工智能机器学习平台(AI Lab):提供丰富的人工智能开发工具和算法模型,帮助开发者快速构建和部署AI应用。产品介绍
  • 物联网开发平台(IoT Explorer):提供全面的物联网设备接入、数据管理和应用开发能力。产品介绍
  • 移动推送服务(信鸽):为移动应用提供消息推送服务,帮助开发者实现消息通知功能。产品介绍
  • 云存储(COS):提供安全、稳定、低成本的云端存储服务,适用于各类数据存储需求。产品介绍
  • 区块链服务(BCS):提供一站式区块链解决方案,帮助企业快速搭建和管理区块链网络。产品介绍
  • 腾讯云元宇宙:腾讯云的元宇宙计划,正在积极探索和研发相关技术和产品,敬请期待。

以上是腾讯云在云计算领域的一些相关产品,可以根据具体需求选择适合的产品进行开发和部署。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

算法-合并两个排序的链表

题目: 输入两个递增排序的链表合并两个链表并使新链表中的结点仍然是按照递增顺序的。例如输入的链表1和链表2如下,合并后的为链表3。...解题思路: 首先可以确定的是,链表1和链表2本身就是递增的,所以合并的过程可以从链表1,2的头结点开始,先比较1,2的头结点中值的大小,将小的值的结点(比如为链表1头结点)作为合并后的链表链表3)...随后可以考虑成链表1的从原链表第二个结点开始,再次重复上面的步骤,这样就变成了一个递归问题。 ? ? ?...return pHead1; 这就是这个代码很巧妙的地方,往往使一行代码两个甚至多个作用,我们举这样的例子: 链表1 : 1 3 链表2 : 2 4 首先执行...(4)新的链表何时链接?

816100

合并两个有序链表

合并两个有序链表,使得合并后的结果仍然是有序的,直观的做法就是从两个链表的首节点开始比较,将其中小的那个链接到新链表之中,(如果不想破坏原链表,那么需要将该节点拷贝一份,然后链接到新链表之中。).../构造L1和L2链表 L1 = Read(); L2 = Read(); //合并L1和L2链表 L = Merge(L1, L2); //合并后的结果 Print(L); printf(...} } if (NULL == p1) { p3->Next = p2; } if (NULL == p2) { p3->Next = p1; } //此处在原节点的基础上合并两个链表...,破坏掉了原链表,使得原链表为空 L1->Next = NULL; L2->Next = NULL; //返回新链表的头指针 return p; } 这种使用双指针的方法,不止在合并链表的时候会用到...————————————————————9.16更新,并不华丽的分割线—————————————————— 下面是链表相对于数组的一些特点。

5.1K20

合并两个排序链表

题意 将两个排序链表合并为一个新的排序链表 样例 给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15->null。...思路 这道题很简单,属于链表的基本操作。 只需要创建一个新的链表与一个指向新链表最后一个节点的指针即可。...当 l1 与 l2 均不为空的情况下,判断 l1 和 l2的大小,把较小值放进新链表的最后一个节点,然后将较小值所处的链表向后移一位,以判断下一个数。...依次循环,直到 l1 或 l2 中有一方为空时,将为空的一方,直接加到新链表后即可。 代码实现 /** * Definition for ListNode....= l2; if (l2 == null) { lastNode.next = l1; } return listNode.next; } } 原题地址 LintCode:合并两个排序链表

1.5K10

合并两个有序链表算法及实现

合并两个有序链表算法及实现 在软件开发中,合并两个有序链表是一种常见的操作。给定两个有序链表,我们需要将它们合并成一个新的有序链表。本文将介绍合并两个有序链表算法原理,并给出相应的代码实现。...问题描述 假设我们有两个有序链表,分别为链表A和链表B。我们需要编写一个算法来将链表A和链表B合并成一个新的有序链表C。...算法原理 合并两个有序链表可以通过比较链表节点的值来实现。我们可以定义一个新的链表C,然后依次比较链表A和链表B中的节点,将较小的节点添加到链表C中。...空间复杂度为O(m+n),递归调用会占用一定的栈空间,随着链表长度的增加,递归次数也会增加。 4. 总结 本文介绍了合并两个有序链表算法原理,并给出了递归方法的代码实现。...合并两个有序链表是一个常见的操作,掌握该算法可以提高代码的效率和可读性。

39820

合并两个有序链表

合并两个有序链表两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ?...由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。...这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可 /** * Definition for singly-linked list....l2 : l1 return listNode.next }; 解法二:递归 思路:如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。...否则,我们要判断 l1 和 l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。

1.4K30

合并两个排序链表

合并两个排序链表 描述 将两个排序链表合并为一个新的排序链表 样例 给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15->null。...那么其实可以比较两个链表当前节点的值,哪个值小,就把它连接在新链表的后面,并将这个链表的当前指针后移一位.知道某一个链表为空,将另一个链表的所有值链接在后面即可....实现代码 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //由于不知道两个链表哪个头结点大,所以自定义一个头结点 ListNode...dummy = new ListNode(-1), cur = dummy; //当两个链表都不为空 while (l1 !...= null) { //将两个链表中较小的当前节点链接在结果链表上,该链表后移一位 if (l1.val < l2.val) { cur.next = l1; l1

1.5K20

合并两个有序链表

题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...具体操作如下: 1、由于需要对比两个链表的头节点,为了让两个链表的头节点的地位与其它节点的地位一样,避免做其它额外的判断处理,这里设定一个虚拟头节点 dummy ,方便后续返回合并后的链表 2、维护一个...它包含的所有元素都比前面已经合并链表中的所有元素都要大。...pre.next = l2; } // 最后返回虚拟节点的 next 指针 return dummy.next; } } 2、C+...+ 代码 // 登录 AlgoMooc 官网获取更多算法图解 // https://www.algomooc.com // 作者:程序员吴师兄 // 代码有看不懂的地方一定要私聊咨询吴师兄呀 class

1.4K80

合并两个有序链表

已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点,即使节点值相同。 注意:不能开辟新空间来存储合并后的链表。...2.非递归实现 算法过程: 输入:两个有序的单链表head1与head2; 输出:合并后的有序单链表mergeHead; 算法描述: (1)如果head1或head2为空链表,则直接返回另外一个链表...{ curList2->next=newNode2; curList2=curList2->next; } } //合并两个有序链表...7 8 ss1 strIn:3 4 5 6 7 8 合并链表: 1 2 3 3 4 5 5 6 7 8 3.递归实现 从上面合并两个有序链表的步骤中可以看出,每次合并的步骤(2)都是一样的,由此我们想到了递归...+算法合并两个有序链表

2.2K21

合并两个有序链表

合并两个有序链表两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...,p2分别指向两个有序链表的头结点,定义一个指针p3始终指向新链表的最后一个节点,定义一个指针ptmp指向新链表的头结点。...每一次循环都比较两个指针指向节点的值,将偏小的节点加到新链表中(若相等则将p2加到新链表中),且较小的链表上的指针往后移动一位。 当p1、p2任意next节点为空时,将非空节点加到新链表中。...7.同步骤4 循环执行,直到一方指针为空跳出循环 将非空指针指向的节点加到已排序的链表里,此时返回ptmp->next即为合并后的链表 代码 /** * Definition for singly-linked...->将原链表指针向后移动->将新链表指针向后移动 当循环结束后,把原链表非空指针指向的节点加到已排序的链表中即可,返回虚拟头结点的next节点,即可得到合并后的有序链表

16420

☆打卡算法☆LeetCode 21、合并两个有序链表 算法解析

一、题目 1、算法题目 “将连个链表合并为一个新的升序链表并返回。” 题目链接: 来源:力扣(LeetCode) 链接:21....合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com) 2、题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ...2: 输入: l1 = [], l2 = [0] 输出: [0] 示例 3: 输入: l1 = [], l2 = [] 输出: [] 二、解题 1、思路分析 这道题可以采用递归解题,首先,我们需要判断两个链表是不是空链表...如果不是的话,就需要判断两个链表谁的头结点的值更小,然后递归地决定下一个添加到结果里的节点。...因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。 空间复杂度: O(n+m) 其中 n 和 m 分别为两个链表的长度。

18130

合并两个有序链表

两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...示例 1: c++代码: 思路1:开辟一个新链表用来存放新的合并后的升序链表,每一次从l1和l2链表分别取出来一个节点,判断两个节点的值哪一个大,大的节点跟在小的节点后面,小的节点尾插到新链表后面...,并且还有判断l1和l2哪个链表长度更长,当出现一个链表遍历完后,另一个链表剩余部分就直接尾插到新链表后面 #include using namespace std; struct...ListNode* newList = new ListNode();//该链表用来存放整合后的数据 ListNode* end = newList;//指向当前链表尾节点...<< "请为l2链表赋值:" << endl; input(l2); cout << "输出l2链表: " << endl; display(l2); cout <<

1.2K30
领券