021 - 合并两个有序链表(merge-two-sorted-lists)

Create by jsliang on 2019-06-05 08:37:00
Recently revised in 2019-06-05 17:31:37

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 官方题解
3.2 解题代码
3.3 执行测试
3.4 LeetCode Submit
3.5 知识补充
3.6 解题思路
四 总结

二 前言

返回目录

将两个有序链表合并为一个新的有序链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。 

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

三 解题

返回目录

3.1 官方题解

返回目录

https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/

解题千千万,官方独一家,上面是官方使用 Java 进行的题解。

小伙伴可以先自己在本地尝试解题,再看看官方解题,最后再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

3.2 解题代码

返回目录

var mergeTwoLists = function (l1, l2) {
  var mergedHead = {
      val: -1,
      next: null
    },
    crt = mergedHead;
  while (l1 && l2) {
    if (l1.val > l2.val) {
      crt.next = l2;
      l2 = l2.next;
    } else {
      crt.next = l1;
      l1 = l1.next;
    }
    crt = crt.next;
  }
  crt.next = l1 || l2;

  return mergedHead.next;
};

3.3 执行测试

返回目录

  • 参数 1
l1 = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 4,
      next: null
    }
  }
}
  • 参数 2
l2 = {
  val: 1,
  next: {
    val: 3,
    next: {
      val: 5,
      next: null
    }
  }
}
  • 返回值
{
  val: 1,
  next: {
    val: 1,
    next: {
      val: 2,
      next: {
        val: 3,
        next: {
          val: 4,
          next: {
            val:5,
            next: null,
          }
        }
      }
    }
  }
}

3.4 LeetCode Submit

返回目录

✔ Accepted
  ✔ 208/208 cases passed (84 ms)
  ✔ Your runtime beats 98.22 % of javascript submissions
  ✔ Your memory usage beats 87.2 % of javascript submissions (35 MB)

3.5 知识补充

返回目录

在这道题的解题知识中,存在一个知识点:链表。

然后因为 jsliang 跟小伙伴们一样,也是 算法与数据结构 的菜鸟,所以网上找了篇文章:

js实现链表: https://www.cnblogs.com/EganZhang/p/6594830.html

jsliang 碰到这种结构的时候,也是挠头抓耳,然后百度找到这篇文章,基本的结构看懂了,所以在这推荐给小伙伴们。

当然,jsliang 立马下单了一本书 《学习 JavaScript 数据结构与算法》,有没用不知道,先买了再说,后面 jsliang 会补上相关的知识点,小伙伴们先看下上面大佬写的文章咯~

3.6 解题思路

返回目录

图

四 总结

返回目录

这样,我们就完成了 21 题的题解,感觉理解出来的话,其实是挺容易实现的。

如果小伙伴们还是有点懵,最好多打印几个 console.log,就清楚它是怎么运行的了!


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-14 21:45:48

results matching ""

    No results matching ""