精华内容
下载资源
问答
  • 合并两个链表

    2020-05-12 16:43:16
    合并两个链表 题目描述: 思路一:迭代 我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里...

    合并两个链表

    题目描述:

    在这里插入图片描述

    思路一:迭代

    在这里插入图片描述
    在这里插入图片描述

    • 我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位
    • 首先,我们设定一个哨兵节点 prehead ,这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针,我们需要做的是调整它的 next 指针。然后,我们重复以下过程,直到 l1 或者 l2 指向了 null :如果 l1 当前节点的值小于等于 l2 ,我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则,我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面,我们都需要把 prev 向后移一位。
    • 在循环终止的时候, l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
        {
            ListNode *pNewHead=new ListNode(0);
            ListNode *prev=pNewHead;
            if(NULL==l1)
                return l2;
            if(NULL==l2)
                return l1;
            while(NULL!=l1&&NULL!=l2)
            {
                if(l1->val<l2->val)
                {
                    prev->next=l1;
                    l1=l1->next;
                }
                else
                {
                    prev->next=l2;
                    l2=l2->next;
                }
                prev=prev->next;
            }
            prev->next=l1==NULL?l2:l1;
            return pNewHead->next;
        }
    };
    
    复杂度分析
    • 时间复杂度:O(n + m)其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)
    • 时间复杂度为 O(n+m)
    • 空间复杂度:O(1)
    思路二:递归

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (l1 == nullptr) {
                return l2;
            } else if (l2 == nullptr) {
                return l1;
            } else 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),其中 nn 和 mm 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)
    • 空间复杂度:O(n + m)其中 n和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m次,因此空间复杂度为 O(n+m)
    展开全文
  • 递归版题解 这题曾经写过,原文点这里,之前对递归的图解有点简单。这次把递归版本重新写了...新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->3->4输出:1->1->2->...

    递归版题解

    这题曾经写过,原文点这里,之前对递归的图解有点简单。

    这次把递归版本重新写了一下,着重于图解部分,将递归怎么一步步调用的,怎么一步步返回的详细画了一遍。

    先来回顾下这道题目吧:
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    示例:

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4

    递归的两个条件:

    1. 终止条件:当l1或者l2中有一个为空时,就返回
    2. 函数内要做什么:如果l1.val小于等于l2.val,那么将l1.next指向 l1的后续节点和l2中较小的一个

    终止条件比较好理解,函数内做的事情就不那么好懂了 l1的后续节点和l2中较小的一个

    如果是 l1.val<=l2.val,我们就能确定一个较小的节点了,也就是l1。因为链表还没结束,我们要继续比较,这时候比较的是l1.next和l2。

    反之,如果是l1.val>l2.val,我们也能确定一个较小的节点,现在是l2.因为链表还没结束,我们继续比较,这时候比较的是l1和l2.next。

    后面就是不断的递归,最终把整个链表给串起来。c9425f3f70bb8b0ce1979028c4b040f3.gif

    java版本如下:

    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //递归的结束条件,如果l1和l2中有一个为空就返回
    if(l1==null || l2==null) {
    return (l1==null)? l2:l1;
    }
    //如果l1的值<=l2的值,就继续递归,比较l1.next的值和l2的值
    //l1.next和l2比较完后,会产生一个更小的节点x,将x加到当前l1的后面
    if (l1.val<=l2.val) {
    l1.next = mergeTwoLists(l1.next,l2);
    return l1;
    //如果l1的值>l2的值,就继续递归,比较l1的值和l2.next的值
    } else {
    l2.next = mergeTwoLists(l1,l2.next);
    return l2;
    }
    }
    }

    python版本如下:

    class Solution(object):
    def mergeTwoLists(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """

    #递归的结束点就是L1或者L2为空就返回
    #如果L1为空就返回L2,L2为空返回L1
    ifnot (l1 and l2):
    return l1 if l1 else l2
    #L1的val<=L2的val,那么继续递归
    #当前L1的next指向一个递归函数
    #意思是L1的下一个和L2哪个大,就作为当前L1的next
    if l1.val<=l2.val:
    l1.next = self.mergeTwoLists(l1.next,l2)
    return l1
    else:
    l2.next = self.mergeTwoLists(l1,l2.next)
    return l2

    时间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度   

    空间复杂度:O(n + m)

    详解执行过程

    我们定义两个链表:1->2->41->3->4
    L1即为第一个链表,L2为第二个链表
    两个链表下方是代码部分,具体如下图所示:f560b51166e64507eb804d8100a43181.png再解释一下上图中代码部分:

    • 第一个if:递归的终止条件,如果链表1为空 或者 链表2为空就返回
    • 第二个if:如果链表1的节点值 <= 链表2的节点值,则继续下一层的递归比较
    • else部分:如果链表1的节点值 > 链表2的节点值,则继续下一层递归比较

    后面我们就开始不断比较,不断调用下一层递归函数
    每一步中,具体执行到哪段代码,我用红色标记出来了:

    635658346a54aa0d262490d90e0bf8be.png5272cdfd24a31b5bda94baa581482cf5.png054181fac19f60408d5704ee084b7ee9.pnge6d188bd875ea784ff450ada153eea69.png2467e71b91d35f0432d1f0503209fe0b.png25505249affca80d58553481e36edbd8.png4bc0842be4bcd12476e57cd8aa15fb93.pngfa29ab5d4c5d88d6ff35175461199bb1.pngdfc9978bd92d725ccfc78e53eb96d5f5.png3576f3d18d46d2c3c14b560d2f104555.png

    <<< 左右滑动见更多 >>>

    • 上图中第一步、第二步:当链表1的节点1 <= 链表2的节点1时候,让链表1的节点1.next指向下一层递归函数,但此时程序并没有执行完,链表1的节点1.next指向的还是一个未知的节点,到底会指向谁,需要等后面的递归函数执行完返回后才知道
    • 第三步、第四步:链表1的节点2>链表2的节点1,让链表2的节点1.next指向下一层递归函数,具体指向谁需要等后面的递归函数执行完返回后才知道
    • 第五步、第六步:链表1的节点2<=链表2的节点3,让链表1的节点2.next 指向下一层递归函数
    • 第七步、第八步:链表2的节点3.next 指向下一层的递归函数
    • 第九步、第十步:链表1的节点4.next 指向下一层递归函数

    经过上面 10 步之后,递归调用就到头了,因为上图中最后一张图,最右边的黑色方框里只剩下一个4了。此时就会触发递归终止条件,然后不断返回

    58606e92fadf7a1f8cc8b4ebfafc850a.pngcaa58504e9c5c1c5ebdbf95189127b11.png0e20bff34f0dd459bf164602b38b1fde.png8f89f2289b1a2a1bc9cc3015d3c7174f.png8623149bdf74eb2f80f772eaca888ee5.png617ab2c4323098b8856cc7462e8c4899.png043150afcf6aea60ef448ecba4635faa.png8729eb9f4c3578817bb48cd3f3c9ed30.png43fd68022f974ae0797e50a4d693cbc8.png1d06f2f78a785f9e3fe9cb013556bb42.png

    <<< 左右滑动见更多 >>>

    再来分析一下上图中递归函数是怎么返回的:

    • 第11步:此时链表1为空,于是触发递归终止条件,返回链表2的节点4
    • 第12步:链表2的节点4返回到上一层递归函数,上一层函数是链表1的节点4,于是链表1的节点4.next 就指向 链表2的节点4
    • 第13步:链表1的节点4返回
    • 第14步:链表2的节点4返回到上一层递归函数,上一层函数是链表2的节点3,于是链表2的节点3.next 就指向 链表1的节点4
    • 第15步:链表2的节点3返回
    • 第16步:链表2的节点3返回到上一层递归函数,上一层的函数是链表1的节点2,于是链表1的节点2.next 就指向 链表2的节点3
    • 第17步:链表1的节点2返回
    • 第18步:链表1的节点2返回到上一层递归函数,上一层函数是链表2的节点1,于是链表2的节点1.next 就指向 链表1的节点2
    • 第19步:链表2的节点1返回
    • 第20步:链表2的节点1返回到上一层递归函数,上一层函数是链表的节点1,于是链表1的节点1.next 就指向 链表2的节点1

    如下图所示,最后返回链表1的节点1,此时两个链表就被合并成一个链表了c14177fde5da1e18d38de3c670b48b70.png

    推荐阅读  点击标题可跳转

    合并两个有序链表

    反转链表

    再谈反转链表递归版

    合并K个排序链表

    看完本文有收获?请转发分享给更多人

    e7bb55c34e47b1f36b6fdf5c2d7bfc71.png

    好文章,我在看❤️

    展开全文
  • #21合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。其中,节点ListNode的结构如下:/** * public class ListNode { * int val; * ListNode next; *...

    #21 合并两个有序链表

    将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。其中,节点ListNode的结构如下:

    /** * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */

    40a1612f6118ad67db8024b3965aa71d.png

    1)递归法

    28e232dac0af3efc8d4950b632327998.gif

    比较两链表头部元素的值的大小,取出值较小的节点L,将 L.next() 与另一队列继续放入函数 mergeTwoLists 中,并返回节点 L 。

    class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null) {            return l2;        }        else if (l2 == null) {            return l1;        }        else if (l1.val < l2.val) {            l1.next = mergeTwoLists(l1.next, l2);            return l1;        }        else {            l2.next = mergeTwoLists(l1, l2.next);            return l2;        }    }}

    2)迭代法

    同样是比较两链表头部元素的值的大小,取出值较小的节点 L 放入输出队列中,并将指向该队列头部的指针向后移动一位,继续比较,直到节点 L 指向 NULL  。

    class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode result = new ListNode(-1);        ListNode temp = result;        while(l1!=null && l2!=null){            if(l1.val<=l2.val){                temp.next = l1;                l1 = l1.next;            }else{                temp.next = l2;                l2 = l2.next;            }            temp = temp.next;            }        if(l1==null) {            temp.next = l2;                }        if(l2==null) {            temp.next = l1;                }                return result.next;     }}

    巷子书城全新上线啦~

    全新码书全场75折

    2cedaf537efe5be1ae2c0cc571e6e033.png

    假期想一起学Java的小伙伴可以加qq群:563347237,相互监督,共同进步。

    6d6a967bb6d9a3e1978a8cc620b36016.gif  【阅读全文】进入练习

    展开全文
  • 序本文主要记录一下leetcode链表之合并两个排序的链表题目输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。示例1:​输入:1->2->4, 1->3->4输出:1->1->2->3->...

    本文主要记录一下leetcode链表之合并两个排序的链表

    fc3ee962176371fb2bd71f2199b46f10.png

    题目

    输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。示例1:​输入:1->2->4, 1->3->4输出:1->1->2->3->4->4​限制:​0 <= 链表长度 <= 1000​来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    题解

    /** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode newHead = new ListNode(-1);        ListNode cursor = newHead;        while(l1 != null && l2 != null) {            if (l1.val <= l2.val) {                cursor.next = l1;                l1 = l1.next;            } else {                cursor.next = l2;                l2 = l2.next;            }            cursor = cursor.next;        }​        if (l1 == null) {            cursor.next = l2;        }​        if (l2 == null) {            cursor.next = l1;        }​        return newHead.next;    }}
    • 这里先创建一个newHead节点来表示合并后链表的头指针,然后创建一个cursor,其初始值为newHead;之后同时遍历l1及l2,取最小的作为cursor.next,同时该链表前进一个节点,并且cursor跟着前进;最后再将cursor.next指向尚未遍历完的链表的剩余节点;之后返回头指针指向的节点

    小结

    合并两个有序链表的基本思路就是设置一个cursor以及新链表的头指针,然后同时遍历两个链表,取小的节点作为cursor的next,然后该链表往前进,cursor也跟着往前进,最后再将cursor.next指向尚未遍历完的链表的剩余节点

    doc

    • he-bing-liang-ge-pai-xu-de-lian-biao-lcof
    展开全文
  • C语言实现合并两个链表 含注释

    千次阅读 2018-04-22 20:58:24
    本例子实现将两个链表合并,合并后的链表是第一个链表。通过将第二个链表连接到第一个...请看代码:/*合并两个链表*/ #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; //声明struct student...
  • 合并两个链表(c++)

    千次阅读 2018-12-09 13:59:26
    合并两个链表(c++) 输入的链表按照其元素从小到大的顺序排序,输出的链表也按从小到大的顺序排序,请合并两个链表 template&lt;typename E&gt; Link&lt;E&gt; * LList&lt;E&gt;::merge...
  • 如何快速合并两个链表这个问题是在面试的时候遇到的,面试官是微软资深CTO周雷先生,面试的时候周先生一共出了三个题目: 1.两个无序的链表将其合并成一个,要考虑用时最少,内存最少(数据结构中的时间复杂度,...
  • 合并两个链表的问题

    2014-06-10 10:37:13
    两种方法合并两个链表
  • 合并两个链表,得到一个新的链表 a = 1->2->3->4 和 b = 2->3->5 合并为 c = 1->2->3->4->5,另外只能返回结果c,不能修改a,b两个链表的数据。 链表元素定义 /** * 链表元素定义 * Create by zxb on 2017/8/27...
  • 逆转交替合并两个链表的解析与实现 本篇文章主要介绍了将两个链表逆转交替合并的实现思路与方法,需要的朋友可以参考下 逆转交替合并两个链表,即从一个链表的尾指针指向另一个链表的尾指针,依次逆转...
  • 【 数据结构】· 合并两个链表

    万次阅读 多人点赞 2017-03-10 15:25:33
    1.实现将两个带头结点的链表L1和L2进行连接,连接后的链表仍然使用原来的存储空间;结果为链表L2连接到L1的末尾。思路:找到链表L1的尾节点,使其指针域指向下一个链表的头结点(同时将链表L2所占用的内存空间进行...
  • 合并两个链表成一个升序链表

    千次阅读 2016-12-12 22:01:49
    两个链表合并成一个升序链表
  • leetcode1669. 合并两个链表

    千次阅读 多人点赞 2021-03-07 17:15:50
    给你两个链表list1 和list2,它们包含的元素分别为n 个和m 个。 请你将list1中第a个节点到第b个节点删除,并将list2接在被删除节点的位置。 下图中蓝色边和节点展示了操作后的结果: 请你返回结果链表的头指针。...
  • 问题描述: 链表A和B A: 1->2->3->4 B: a->b->c->d 请逆转交替合并两个链表,示例结果如下: 4->d->3->c->2->b->1->a
  • leetcode21 合并两个链表

    千次阅读 2019-12-02 21:37:46
    新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 思路:链表归并。 /** * Definition for singly-linked list. * ...
  • 合并两个链表,去掉重复元素

    千次阅读 2015-04-14 16:02:19
    最近在学习机器学习的相关算法,写到DbScan算法发现在簇扩展时用到两个邻域中的点会重合,于是尝试了合并两个链表的两个算法。 最初用到这个方法,认为它简单易用。思路是定义一个链表存放合并后的链表list,首先往...
  • Java合并两个链表

    2020-04-05 17:46:17
    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 递归思想 如果list1小于list2,则list1作为新序列的开头,后面应该接的部分等同于list1.next和list2的重新排序。...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 题目解析: 首先,我们设定一个哨兵节点 prehead ,这可以在最后让我们比较...
  • 三个链表面试题目综合:找到链表倒数K个节点、链表逆转、合并两个链表。 #include using namespace std; typedef struct linklist{ linklist *link; int val; }*listPoint; //按节点值升序插入链表 void insert...
  • LeetCode - 合并两个链表

    千次阅读 2018-04-13 23:06:25
    新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4 解法 // 遍历解法 // 同时...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 代码...
  • 合并两个链表并排序

    2017-10-14 20:35:07
    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 ...
  • 数据结构 合并两个链表

    千次阅读 2009-11-21 02:09:00
    1、合并两个链表问题描述:设A与B分别为两个带有头结点的有序循环链表(所谓有序是指链接点按数据域值大小链接,本题不妨设按数据域值从小到大排列)。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,279
精华内容 5,311
关键字:

合并两个链表