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

    千次阅读 2019-04-28 19:30:55
    合并两个有序链表 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->...

     合并两个有序链表

    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
    

    迭代法:

    /**
     * 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) {
               // 两条链表都为null 直接返回null
              if(l1==null&&l2==null)
                return null;
              if(l1==null) // l1为null 直接返回l2
                return l2;
              if(l2==null) // l2 为null, 直接返回l1
                return l1;
            // cur 保存当前尾节点 temp 保存即将接上的节点  head 为头结点
              ListNode cur=null,temp=null,head=null;
              while(l1!=null&&l2!=null)
              {
                    if(l1.val>=l2.val)
                    {
                        temp = l2;
                        l2 = l2.next;
                    }
                    else
                    {
                        temp = l1;
                        l1 = l1.next;
                    }
                    if(head==null)
                        cur = head = temp;
                    else
                    {
                        cur.next = temp;
                        cur = temp;
                    }
                }
              if(l1==null)
                cur.next = l2;
              else
                cur.next = l1;
              return head;
        }
    }

    递归法:

    /**
     * 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) {
            if(l1==null)
                return l2;
            if(l2==null)
                return l1;        
            if(l1.val>=l2.val)
            {
                l2.next = mergeTwoLists(l1,l2.next);
                return l2;
            }else
            {
                l1.next = mergeTwoLists(l1.next,l2);
                return l1;
            }
    
        }
    }

     

    展开全文
  • Java合并两个有序链表

    2019-07-31 13:11:13
    要求:给出链表 1 → 1 → 2 → 3 → null 和 1 →...思路:用两个引用 cur1 和 cur2 同时遍历两个链表;当 cur1.value 小于或者等于 cur2.value 时,把 cur1 尾插到结果链表 resultList 上;在尾插时需要分结果链表...

    要求:给出链表 1 → 1 → 2 → 3 → null 和 1 → 2 → 4 → 6 → null;要求输出结果为
    1 → 1 →1 → 2 → 2 → 3 → 4 → 6 → null
    思路:用两个引用 cur1cur2 同时遍历两个链表;当 cur1.value 小于或者等于 cur2.value 时,把 cur1 尾插到结果链表 resultList 上;在尾插时需要分结果链表为空和结果链表不为空两种情况。如果两个链表都还有结点,选择小的一个尾插到结果链表上;直到一个链表全部结点都处理完了,把另一个链表额剩余部分接到结果链表尾部。
    完整调式程序
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    时间复杂度:O(n)

    展开全文
  • 【Leetcode刷题实录】合并两个有序链表生命不息,折腾不止Hello,大家好!这是LeetCode刷题实录的第一期,今天的这道题目是合并两个有序链表,在LeetCode中是第二十一题,欢迎大家在看完题解以后直接去上手做一下,...

    【Leetcode刷题实录】合并两个有序链表

    生命不息,折腾不止

    Hello,大家好!

    这是LeetCode刷题实录的第一期,今天的这道题目是合并两个有序链表,在LeetCode中是第二十一题,欢迎大家在看完题解以后直接去上手做一下,毕竟看的再多也不如自己去实操一下,可能有些同学在在做这道题之前,并不知道链表这种数据结构是什么样子,在这先给大家介绍一下什么是链表。

    链表大致可以分为单链表,双向链表,循环链表

    那对链表的定义是什么呢?

    链表是由一组不必相连【不必相连:可以连续也可以不连续】的内存结构 【节点】,按特定的顺序链接在一起的抽象数据类型。

    再简单用一句话概括可以为:

    一个对象指向对另外一个对象的引用

    具体可看下图:

    a31a1a3b98818afb42d07d0744bebe95.png

    到这现在大家应该对链表有了一定的了解了,废话不多说,现在开始今天的题目。

    题目描述:

    合并有序链表(Merge Two Sorted Lists)

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

    示例:

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

    题目解析:

    首先分析题目,题中给出的关键条件是有序,并且两个链表的长度是不固定的,可能会出现的情况是一个链表有多个,另外一个链表直接为空。因为两个链表是有序的,所以就直接比较两个链表的头结点,谁更小就将谁放在前面。做这道题的时候就是一直进行比较,那个更小就放在前面,在比较过程中,如果有一方为空,剩下的链表就可以直接拼接到结果链表之后(因为有序)

    这道题可以有两种题解:一种是递归,另外一种是迭代

    递归结题法:

    ① 使用递归,首先要知道递归的终止条件是什么,这道题的终止条件就是当两条链表中的其中一个为空的时候结束循环。则设两条链表分别名为 l1 和 l2,当 l1 为空或 l2 为空时结束

    ② 递归的内容是,比较l1和l2的节点值,如果l1更小,则返回l1,l1.next和l2继续比较,l2原理同。

    代码实现:

    e841e75f1699942444af94a9a2c2f0bc.png

    迭代解题法:

    ①使用迭代去解题的好处是更容易理解题目,使用迭代去解题的终止条件同样是有一方为空时,结束循环。

    ②在迭代过程中去创建一个哑结点,使用哑结点来连接已经排序好的链表,最后返回哑结点下一个引用。使用while循环链表,当有一方链表为空,则将剩余链表拼接到已经排序好的链表后,结束循环。

    代码实现:

    eb0ddfb0ee157ae013ed9b73d5c9a11c.png

    本文由博客群发一文多发等运营工具平台 OpenWrite 发布

    展开全文
  • 本文实例讲述了JS实现的合并两个有序链表算法。分享给大家供大家参考,具体如下:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->...

    本文实例讲述了JS实现的合并两个有序链表算法。分享给大家供大家参考,具体如下:

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

    示例:

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

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

    576fcf0935fa2ace3aa551d6f8bc299b.png

    可以直接运行的方案:

    function Node(element) {

    this.element = element;//当前节点的元素

    this.next = null;//下一个节点链接

    }

    function List() {

    this.head = new Node("head");//头节点

    this.find = find;//查找节点

    this.insert = insert;//插入节点

    this.remove = remove;//删除节点

    this.display = display;//显示链表

    this.findPrevious = findPrevious; //查找前一个节点

    }

    //下面的函数是操作方法:对应List类构造函数中的名称

    //查找给定节点

    function find(item) {

    var currNode = this.head;

    while(currNode.element != item) {

    currNode = currNode.next;

    }

    return currNode;

    }

    //向链表插入一个节点

    function insert(newElement,item) {

    var newNode = new Node(newElement);

    var current = this.find(item);

    if(current == null)

    return console.log("can't find the item");

    newNode.next = current.next;

    current.next = newNode;

    }

    //删除节点

    function remove(item) {

    var prevNode = this.findPrevious(item);

    if(prevNode.next != null)

    prevNode.next = prevNode.next.next;

    }

    //从链表中删除节点时,我们先要找个待删除节点的前一个节点,找到后,我们修改它的 next 属性,使其不在指向待删除的节点,而是待删除节点的下一个节点。那么,我们就得需要定义一个 findPrevious 方法遍历链表,检查每一个节点的下一个节点是否存储待删除的数据。如果找到,返回该节点,这样就可以修改它的 next 属性了。

    //查找带删除节点的前一个节点

    function findPrevious(item) {

    var currNode = this.head;

    while(currNode.next != null && currNode.next.element != item) {

    currNode = currNode.next;

    }

    return currNode;

    }

    //显示链表元素

    function display() {

    var current = this.head;

    while(current.next != null) {

    console.log(current.next.element);

    current = current.next;

    }

    }

    /**

    * @param {Node} l1

    * @param {Node} l2

    * @return {Node}

    */

    var mergeTwoLists = function(l1, l2) {

    // 模仿链表的数据结构

    var mergedHead = { element : -1, next : null },

    cur = mergedHead;

    while (l1 && l2){

    if(l1.element <= l2.element){

    cur.next = l1;

    l1 = l1.next;

    }

    else {

    cur.next = l2;

    l2 = l2.next;

    }

    cur = cur.next;

    }

    cur.next = l1 || l2

    return mergedHead.next;

    };

    let list1 = new List();

    list1.insert(1,'head');

    list1.insert(2,1);

    list1.insert(4,2);

    console.log(list1.display());

    let list2 = new List();

    list2.insert(1,'head');

    list2.insert(3,1);

    list2.insert(4,3);

    console.log(list2.display());

    console.log(mergeTwoLists(list1.head,list2.head))

    感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码,查看运行效果。

    希望本文所述对大家JavaScript程序设计有所帮助。

    展开全文
  • 两个无序单链表,排序后合并成一个有序链表算法思想:用冒泡法,对链表1和2进行排序,对排序后的两个链C/C++两个无序单链表,排序后合并成一个有序链表算法思想:用冒泡法,对链表1和2进行排序,对排序后的两个链表...
  • 前面的文章写了合并两个有序的数组,然后想着顺便写一下合并两个有序的单链表。增加自己对这些数据结构操作的熟练度,让自己有更清晰的认识。先上代码:public class TwoListToOne {public static void main(String...
  • 实现思路 1.传入两个链表的头结点 ...4.如果有一个链表已经为空,那么就只是针对另一个链表进行添加即可,知道两个链表都为空。 代码实现 public class SingleLinkedList { private Person head = ...
  • 题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 思路: 递归 终止条件...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&gt;4-&...
  • 合并两个有序链表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-&...
  • 合并两个有序链表 解法一:双指针法时间复杂度:O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度空间复杂度:O(1) 双指针,常数级别复杂度/***Definitionforsingly-linkedlist.*functionListNode(val)...
  • 21. 合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 :输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4来源:...
  • 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务...今天和大家聊的问题叫做合并两个有序链表,我们先来看题面:https://leetcode-cn.com/problems/merge-two-sorted-lists/Merge two sorted ...
  • 两个有序链表合并为一个有序链表 思路: 1.必须保证两个链表为有序链表 2.在两个链表都不为空的条件下,设一个 last=null; (1)如果链表1的值小于等于链表2的值,进行循环,先放链表1的值到新链表result,...
  • 先来回顾下这道题目吧:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->3->4输出:1->1->2->...
  • 问题:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例:输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4这是一道非常经典的链表...
  • 请问如何创建“publicstaticSortedListmergeList(SortedListlist1,SortedListlist2)”方法,该方法可以合并两个有序链表成为一个新的有序链表。程序应该遍历每个链表的元素然后直接把...请问如何创建“public static...
  • 利用递归法将两有序链表合并成链表,且合并后的链表仍然有序。 比较链表1和链表2的第一结点数据,如果head1.data&lt;head2.data,则把结果链表头指向链表1的第一结点。 对剩余的head1.next和链表2再次递归...
  • Java实现 LeetCode 21 合并两个有序链表

    千次阅读 2020-02-12 15:29:00
    21. 合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例...
  • 点击上方"蓝字",关注了解更多合并两个有序链表1. 题目描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。2. 示例无3. 解题思路思路:非递归比较两个链表的首...
  • java中将两个有序链表合并为一个有序链表: 1.必须保证两个链表为有序链表 2.在两个链表都不为空的条件下,设一个 last=null; (1)如果链表1的值小于等于链表2的值,进行循环,先放链表1的值到新链表result,...
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解析: 本题考虑递归解法,依次判断 l1 和 l2 哪个链表的结点更小,使用较小的结点指针指向其余节点的合并结果...
  • 因为这两个链表都是有序的,先比较两个链表的第一项, 比较小的那一项跟在傀儡结点的后面,较大的则跟下一项进行比较。 当有链表为空时,直接将node.next等于另一链表的剩余结点。 代码如下: public ListNode ...

空空如也

空空如也

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

java合并两个有序链表

java 订阅