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

我正在尝试以升序将两个链表合并为1个链表

将两个链表合并为一个链表的算法可以使用迭代或递归方法。

方法1:迭代 迭代方法通过比较两个链表的节点值,将较小的节点依次加入到新链表中。具体步骤如下:

  1. 创建一个新的链表作为结果链表的头部,以及一个指针指向当前结果链表的末尾。
  2. 初始化两个指针分别指向两个链表的头部。
  3. 进行循环,直到两个链表都遍历完: 1)比较两个链表当前节点的值,将较小的节点加入到结果链表中。 2)更新指针,将当前节点后移。
  4. 如果其中一个链表已经遍历完,将另一个链表剩余的节点直接加入到结果链表中。
  5. 返回结果链表。

具体代码如下(使用Python语言):

代码语言:txt
复制
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)  # 创建结果链表的头部
    curr = dummy  # 当前结果链表的指针

    while l1 and l2:  # 迭代直到两个链表都遍历完
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    # 将剩余的链表连接到结果链表的末尾
    curr.next = l1 if l1 else l2

    return dummy.next  # 返回结果链表的头部

方法2:递归 递归方法通过不断比较两个链表的头节点,将较小的节点加入到结果链表中,并递归地处理剩下的节点。具体步骤如下:

  1. 如果其中一个链表为空,直接返回另一个链表作为结果。
  2. 比较两个链表的头节点的值,将较小的节点作为结果链表的头节点。
  3. 递归调用合并函数,将较小节点的下一个节点与另一个链表进行合并,并将结果连接到较小节点的下一个节点。
  4. 返回结果链表的头节点。

具体代码如下(使用Python语言):

代码语言:txt
复制
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    if not l1:
        return l2
    if not l2:
        return l1
    
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

这两种方法都可以实现将两个链表合并为一个链表的功能。它们的时间复杂度都是O(n + m),其中n和m分别为两个链表的长度。

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

相关·内容

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

大家好,是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。...一、题目 1、算法题目 “连个链表并为一个新的升序链表并返回。” 题目链接: 来源:力扣(LeetCode) 链接:21....合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com) 2、题目描述 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ...如果不是的话,就需要判断两个链表谁的头结点的值更小,然后递归地决定下一个添加到结果里的节点。...因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。 空间复杂度: O(n+m) 其中 n 和 m 分别为两个链表的长度。

19230
  • ​LeetCode刷题实战21:合并两个有序链表

    算法的重要性,就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !...今天和大家聊的问题叫做合并两个有序链表,我们先来看题面: https://leetcode-cn.com/problems/merge-two-sorted-lists/ Merge two sorted...题意 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...样例 输入:1->2->4, 1->3->4输出:1->1->2->3->4->4 题解 两个有序链表的排序,实际上可以看成一个单链表使用归并排序的最后一个环节:“两个排好序的子序列合并为一个子序列:...好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是最大的动力。

    25230

    一般是面试的热身题——LeetCode题目21:合并两个有序链表

    原题描述 + 两个升序链表并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...当时还挺惊讶的,因为这道题几乎毫无难度,在纸上写这道题的时候就在想,面试官是不是要出什么幺蛾子,事实证明的担心是对的,因为他后面把这道题改了一下让继续做。至于改版的题目在之后的文章会讲。...现在回到这道题目,思路很简单: 先创建一个哑结点(头结点),它将指向合并的新链表; 使用两个指针指向两个链表表头,不断相互比较,每次取较小的节点进行合并,然后对应的指针后移,不断重复这个过程; 大概率有一个链表先遍历完...想提几个点: 题目是合并已有的链表,千万千万别自己创造新的链表; 遇到链表的题目请优先考虑创建哑结点,这很方便。...将上述刚刚被连接的节点指针后移一步,继续比较,连接,直到某个链表被完全遍历; ? 此处省略若干步,直到下面的状态; ? 4. 最后,未被完全遍历链表的剩余部分直接相连即可。 ?

    50810

    合二为一

    合并有序链表 题目:两个升序链表并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...迭代法: 因为我们有两个升序链表,我们需要将其合并,那么我们需要创建一个新节点(headpro),然后我们利用双指针思想,每个链表放置一个指针,然后进行遍历并对比当前指针指向的值。...然后headpro.next指向较小值的那个节点,不断迭代,直至到达某一有序链表底部,此时一个链表遍历完成,然后我们未完全遍历的链表接在我们接在合并链表之后即可。...l1 = l1.next; } headpro = headpro.next; } //没有遍历完的添加到尾部...合并两个有序链表 大家如果觉得这篇文章对大家有帮助的话,就请你将它转发给需要的人吧,顺便请大家点个关注和在看吧,创作不易。你们的支持对真的帮助很大!

    25010

    合并链表与生成括号——LeetCode 21、22 题记

    题目一 第 21 题 合并两个有序链表两个升序链表并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 思路 基于以往经验,这里就可以把两个链表同时放到一个遍历循环中,判断条件就是其中任意链表还没有结束,这样就可以一个循环遍历两条链表所有节点...这个穷举过程,因为 n 不确定,如果要穷举的话,目前能想到的只有 n 层 for 循环来嵌套,但这个写不出来,纠结了好几个小时也写不出来。对于递归法,又理解得不到位,抓瞎了。...那么相应的优化可以放到递归生成单一结果的过程中,在生成结果时就保证它是规的,那么就可以规避掉后续不符合规则的诸多情况。...,现在可以独立来解决了,但可能仍需配合着测试用例来进行调试;生成括号的这道中等难度题目,目前对递归法和回溯法仅停留在可以理解的阶段,要多练习写写这类的代码。

    69010

    【每日leetcode】4.合并有序链表

    ——leetcode此题热评 前言 xdm,现在是早上8:14,窗外下着小雨 是一条,在做leetcode第21题 加油!...Question 难度:简单 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...= [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 提示: 两个链表的节点数目范围是...异曲同工 忘记的小伙伴可以先看一下 传送门 当l1 和l2 都不是空链表时,判断l1 和l2 哪一个链表的头节点的值更小,较小值的节点添加到结果里。...非空链表接在合并链表的后面 对于链表操作,一般都需要维护一个当前节点的指针,可以再点击阅读原文回看一下两数相加帮助理解 Code 所有leetcode代码已同步至github https://github.com

    36230

    合并两个有序链表(难度:简单)

    一、题目 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...1,3,4] 【输出】[1,1,2,3,4,4] 示例 2: 【输入】l1 = [], l2 = [] 【输出】[] 示例 3: 【输入】l1 = [], l2 = [0] 【输出】[0] 提示: • 两个链表的节点数目范围是...[0, 50] • -100 <= Node.val <= 100 • l1 和 l2 均按 非递减顺序 排列 三、解题思路 因为题目中已经描述了,list1和list2是两个升序链表。...所以,如果要拼装全新的升序列表,只需要对比两个链表中的值即可。此时需要两个指针list1和list2分别指向两个链表的对比节点。...具体逻辑如下图所示: 当list1和list2长度不同的时候,为了简化操作,可以“多余”的部分直接拼装到新链表即可。

    15730

    ​LeetCode刷题实战23:合并K个升序链表

    算法的重要性,就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !...今天和大家聊的问题叫做合并K个升序链表,我们先来看题面: https://leetcode-cn.com/problems/merge-k-sorted-lists/ Given an array of...题意 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...] 将它们合并到一个有序链表中得到。...cur.next; } return dummyHead.next; } } 好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是最大的动力

    24420

    【面试高频系列】一道结合「简单数据结构 & 简单算法」的面试题 ...

    合并两个有序链表」,难度为 「Easy」。 两个升序链表并为一个新的「升序链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: ?...= [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 提示: 两个链表的节点数目范围是...两数相加(中等) 讲过啦,让三叶来帮你回忆一下: 做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。...空间复杂度: 最后 这是我们「刷穿 LeetCode」系列文章的第 No.21 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们先将所有不带锁的题目刷完...为了方便各位同学能够电脑上进行调试和提交代码,建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

    43120

    Leetcode No.21 合并两个有序链表

    一、题目描述 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。...然后,我们重复以下过程,直到 l1 或者 l2 指向了 null :如果 l1 当前节点的值小于等于 l2 ,我们就把 l1 当前的节点接在 prev 节点的后面同时 l1 指针往后移一位。...不管我们哪一个元素接在了后面,我们都需要把 prev 向后移一位。 在循环终止的时候, l1 和 l2 至多有一个是非空的。...由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地非空链表接在合并链表的后面,并返回合并链表即可。

    28610

    C语言每日一题(29)合并两个有序链表

    力扣网 21合并两个有序链表 题目描述 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...示例 思路分析 最基本的一种思路就是,遍历两个链表,将对应结点的值进行比较,题目要求是要升序排序,即较小的值先排在前面,随后所在链表的较小结点先走,后面的值于第二个链表的结点进行比较,即谁小谁先排,谁小谁先动...需要注意的是: 会存在比较存放完后,其中一个链表会有剩余,此时不需要再进行比较,直接进行存放即可。...ListNode*)malloc(sizeof(struct ListNode));//哨兵位 struct ListNode* cur1=list1,*cur2=list2;//避免头结点丢失,使用两个指针代替遍历...tail=tail->next; cur1=cur1->next; } } if(cur1==NULL)//判断是否存在任一链表有剩余的情况

    11910

    合并两个有序链表(简单)

    题目描述 两个升序链表并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ?...= [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 提示: 两个链表的节点数目范围是...O(1) ---- 最后 这是我们「刷穿 LeetCode」系列文章的第 No.21 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们先将所有不带锁的题目刷完...由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 21/1916 。...为了方便各位同学能够电脑上进行调试和提交代码,在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

    28110
    领券