精华内容
下载资源
问答
  • 合并两个有序链表No more than a platitudeMerge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.Example:Input: 1-&...

    925f747f9470586df645cac86725d1c3.png

    合并两个有序链表

    No more than a platitude

    Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

    Example:

    Input: 1->2->4, 1->3->4
    Output: 1->1->2->3->4->4

    Mine

    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode head = new ListNode(0);// 虚表头
            ListNode point = head;
           while (l1 != null && l2 != null) {
                if(l1.val <= l2.val){
                // 不断让表接上头
                    point.next = l1;
                    point = point.next;
                    l1 = l1.next;
                }    
                else {
                    point.next = l2;
                    point = point.next;
                    l2 = l2.next;
                }
           }
           if (l1 == null) {
               point.next = l2;
            } 
            else {
               point.next = l1;
            }
        return head.next;    
    
        }
    }
    我开始是准备重置两个指针互相捣腾。然后返回最原先设定的那个表头。但是做了半天发现没有办法解决有连续数字的问题,然后就是这种重新建两个指针,让本来的表头互相捣腾。方便多了。

    官方答案都差不多就不贴了

    展开全文
  • 合并两个有序链表 解法一:双指针法时间复杂度:O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度空间复杂度:O(1) 双指针,常数级别复杂度/***Definitionforsingly-linkedlist.*functionListNode(val)...

    合并两个有序链表

    解法一:双指针法

    • 时间复杂度:O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度
    • 空间复杂度:O(1) 双指针,常数级别复杂度
    /**
    * Definition for singly-linked list.
    function ListNode(val) {
    *     this.val = val;
    *     this.next = null;
    * }
    */
    /**
        * @param {ListNode} l1
        * @param {ListNode} l2
        * @return {ListNode}
        */
    var mergeTwoLists = function(l1, l2) {
        var prevHead = new ListNode(-1);
        var prevNode = prevHead;
        while (l1 != null && l2 != null) {
            if(l1.val <= l2.val){
                prevNode.next = l1; 
                l1 = l1.next
            }else{
                prevNode.next = l2;
                l2 = l2.next;
            }
            prevNode = prevNode.next;
        }
        prevNode.next = l1 ? l1 :l2;
        return prevHead.next;
    };

    解法二:递归

    • 时间复杂度:O(n)(n为l1和l2的每个元素的遍历次数和)
    • 空间复杂度:O(n)(n为l1和l2的空间和)

    编程技巧:递归 + 原地斩链相连

    • 递归比较查看两个链表哪个元素先小 就斩断此元素位置链条⛓️连接到另一链表上 如此也不需要另外开辟存储空间
    • 斩断后 重连铁链的动作因为要自动非人工 所以需要程序自己调用自己 即为递归
    • 斩断后需要连的结点 通过 return 最小结点 即动态更新 斩断结点位置
    • 随时连接下一个符合要求的位置(x.next = 求下一个需要连接的结点位置(即程序自动搜索即递归) && x = 下一个需要连接的结点位置)
    • 返回修改后的 l1头结点的链表 或 l2头结点的链表
    /**
    * Definition for singly-linked list.
    * function ListNode(val) {
    *     this.val = val;
    *     this.next = null;
    * }
    */

    /**
    @param {ListNode} l1
    @param {ListNode} l2
    @return {ListNode}
    */

    var mergeTwoLists = function(l1, l2{
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

    参考

    function ListNode(val = 0, next = null{
      this.val = val;
      this.next = next;
    }

    var mergeTwoLists = function (l1, l2{
      var obj = new ListNode(-1);
      var point = obj; // 存放obj指针
      while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
          point.next = l1;
          l1 = l1.next;
        } else {
          point.next = l2;
          l2 = l2.next;
        }
        point = point.next;
      }

      point.next = l1 ? l1 : l2;

      return obj.next;
    };

    var l1 = {
      val1,
      next: {
        val2,
        next: {
          val3,
          nextnull
        }
      }
    };
    var l2 = {
      val1,
      next: {
        val3,
        next: {
          val5,
          nextnull
        }
      }
    };

    console.log(mergeTwoLists(l1, l2));
    bfbc9757a528b371176bf05513edf674.png
    展开全文
  • 21. 合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 :输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4来源:...

    ec1ada206e89b96d014456067028ba83.png

    21. 合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    示例 :

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

    来源:力扣(LeetCode) 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    题解:

    本题想法比较简单,就是创建一个新链表,然后遍历两个链表结点,哪个结点值小就往新链表后面接。

    具体代码如下:

    /**
     * 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 dummy = new ListNode(0);
            ListNode temp = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val > l2.val) {
                    temp.next = l2;
    
                    l2 = l2.next;
                } else {
                    temp.next = l1;
    
                    l1 = l1.next;
                }
                temp = temp.next;
            }
    
            temp.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }

    本题还有一种递归的思路,这里给出了详细解释https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/

    具体代码如下:

    /**
     * Definition for singly-linked list.
     * 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; }
     * }
     */
    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;
            }
        }
    }
    展开全文
  • 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务...今天和大家聊的问题叫做合并两个有序链表,我们先来看题面:https://leetcode-cn.com/problems/merge-two-sorted-lists/Merge two sorted ...

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

    今天和大家聊的问题叫做合并两个有序链表,我们先来看题面:

    https://leetcode-cn.com/problems/merge-two-sorted-lists/

    Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

    题意

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    样例

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

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

    题解

    两个有序链表的排序,实际上可以看成一个单链表使用归并排序的最后一个环节:“将两个排好序的子序列合并为一个子序列:每次都是从未比较的两个子序列的最小值中选出一个更小值”。

    /**
     * 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 temp=new ListNode(0);
            ListNode head=temp;//保留头节点的引用while(l1!=null&&l2!=null){if(l1.val           {
                   temp.next=l1;
                   l1=l1.next;
               }else
               {
                   temp.next=l2;
                   l2=l2.next;
               }
               temp=temp.next;
            }if(l1==null) temp.next=l2;//l1子序列为空,则直接拼届l2if(l2==null) temp.next=l1;return head.next;//返回头节点指向的序列
        }
    }

    本题还有其他的解法,没有一一介绍,大家可以去LeetCode上学习一下 。好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

    上期推文:

    LeetCode刷题实战1:在数组上遍历出花样

    LeetCode刷题实战2:用链表模拟加法

    LeetCode刷题实战3:最长不重复子串

    LeetCode刷题实战4:两个正序数组的中位数

    LeetCode刷题实战5:判断回文子串

    LeetCode刷题实战6:Z字形变换

    LeetCode刷题实战7:整数反转

    LeetCode刷题实战8:字符串转换整数

    LeetCode刷题实战9:求解回文数

    LeetCode刷题实战10:字符串正则匹配

    LeetCode刷题实战11: 盛最多水的容器

    LeetCode刷题实战12: 整数转罗马数字

    LeetCode刷题实战13: 罗马数字转整数

    LeetCode刷题实战14: 最长公共前缀

    LeetCode刷题实战15:三数之和

    LeetCode刷题实战16: 最接近的三数之和

    LeetCode刷题实战17: 电话号码的字母组合

    LeetCode刷题实战18: 四数之和

    LeetCode刷题实战19:删除链表的倒数第N个节点

    LeetCode刷题实战20:有效括号

    c4a282ce3a2cd11c56dded89e62f9ba9.png

    展开全文
  • 问题:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例:输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4这是一道非常经典的链表...
  • 合并两个有序链表 java 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 : 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;...
  • 点击上方"蓝字",关注了解更多合并两个有序链表1. 题目描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。2. 示例无3. 解题思路思路:非递归比较两个链表的首...
  • 先来回顾下这道题目吧:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->3->4输出:1->1->2->...
  • 合并两个有序链表1. 题目描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。2. 示例无3. 解题思路思路:非递归比较两个链表的首结点,哪个小的的结点则合并到第...
  • //合并两个有序链表 public class MergeTwoLists { public static void main(String[] args) { ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(4); ...
  • 合并两个有序链表题目链接描述示例代码 题目链接 https://leetcode-cn.com/problems/merge-two-sorted-lists/ 描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 两个有序链表的...
  • 合并两个有序单链表,其实就是归并排序。 归并排序:先创建一个新链表,长度是两个单链表之和。然后比较两个单链表的第一个数,把数小的放入新链表,然后指针后移一位,依次比较,当某个链表遍历完了,把另一个链表...
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 public ListNode ...
  • 21. 合并两个有序链表 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 思路很...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 原代码: /** * Definition ...
  • 对于 l1 , l2 两个链表来说,要组成一个升序的链表,那就是要把每一个去对比,得到小的那个节点,然后在用小的节点的下一个继续做对比,这样子递归的想法就出来了 第一步当然是判断两个链表是否都为空,都为空则返回...
  • leetcode分类下所有的题解均为...将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->...
  • 种解法:递归和新建链表 新建一个链表: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ...
  • 两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 想法 这道题很像合并K个排序...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 635
精华内容 254
关键字:

合并两个有序链表java

java 订阅