LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)

Create by jsliang on 2019-07-04 10:32:24
Recently revised in 2019-07-04 16:40:14

一 目录

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

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | | 四 执行测试 | | 五 LeetCode Submit | | 六 解题思路 |

二 前言

  • 难度:简单

  • 涉及知识:链表

  • 题目地址:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

  • 题目内容

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)

在节点 c1 开始相交。

示例 1:

LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)

  1. 输入:intersectVal = 8,

  2. listA = [4,1,8,4,5],

  3. listB = [5,0,1,8,4,5],

  4. skipA = 2,

  5. skipB = 3

  6. 输出:Reference of the node with value = 8

  7. 输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。

  8. 从各自的表头开始算起,链表 A [4,1,8,4,5],链表 B [5,0,1,8,4,5]。

  9. A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)

  1. 输入:intersectVal = 2,

  2. listA = [0,9,1,2,4],

  3. listB = [3,2,4],

  4. skipA = 3,

  5. skipB = 1

  6. 输出:Reference of the node with value = 2

  7. 输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。

  8. 从各自的表头开始算起,链表 A [0,9,1,2,4],链表 B [3,2,4]。

  9. A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)输入:

  1. intersectVal = 0,

  2. listA = [2,6,4],

  3. listB = [1,5],

  4. skipA = 3,

  5. skipB = 2

  6. 输出:null

  7. 输入解释:从各自的表头开始算起,链表 A [2,6,4],链表 B [1,5]。

  8. 由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA skipB 可以是任意值。

  9. 解释:这两个链表不相交,因此返回 null

  注意:

如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码

  1. var getIntersectionNode = function(headA, headB) {

  2. if (!headA || !headB) {

  3. return null;

  4. }

  5. let a = headA,

  6. b = headB;

  7. // 相交则返回当前节点,否则返回 null

  8. // 当 a、b 不相交时:

  9. // 1. 如果 a 为 null,将 headB 赋值给 a;

  10. // 2. 如果 b 为 null,将 headA 赋值给 b;

  11. while (a !== b) {

  12. a = a ? a.next : headB;

  13. b = b ? b.next : headA;

  14. }

  15. return a;

  16. };

四 执行测试

  1. let base = {

  2. val: 8, next: {

  3. val: 4, next: {

  4. val: 5, next: null,

  5. },

  6. },

  7. };

  8. let headA = {

  9. val: 4, next: {

  10. val: 1, next: base,

  11. },

  12. };

  13. let headB = {

  14. val: 5, next: {

  15. val: 0, next: {

  16. val: 1, next: base,

  17. },

  18. },

  19. }

五 LeetCode Submit

  1. Accepted

  2. 45/45 cases passed (124 ms)

  3. Your runtime beats 84.62 % of javascript submissions

  4. Your memory usage beats 49.21 % of javascript submissions (42.9 MB)

六 解题思路

首先,拿到题目,我怀疑题目又有问题了,尝试了下 test,显示为:

  1. Input data:

  2. 8

  3. [4,1,8,4,5]

  4. [5,0,1,8,4,5]

  5. 2

  6. 3

  7. Actual

  8. runtime: 72 ms

  9. answer: No intersection

  10. stdout: ''

  11. Expected

  12. runtime: 28 ms

  13. answer: Intersected at '8'

  14. stdout: ''

然而给我的代码是:

  1. var getIntersectionNode = function(headA, headB) {

  2. // 代码

  3. };

闹哪样呢!为什么它有那么多参数,我只有两个!

而且, [4,1,8,4,5][5,0,1,8,4,5],不是在 1 就相同了吗?怎么是 8 才相交!摔!!!

然后,仔细思考一下……卧槽,它说的相同,不会是地址相同吧?

小伙伴们都知道,在 JS 中,如果是 Number、String 等的复制,是通过传值来实现的;而 Array、Ojbect 等,是通过传址来实现了,看例子:

  1. let a = 1;

  2. let b = a;

  3. b = 2;

  4. console.log(a); // 1

  5. let c = [1, 2, 3];

  6. let d = c;

  7. d.push(4);

  8. console.log(c); // [1, 2, 3, 4]

在这里,我们修改 b 的时候, a 是不会发生对应改变的。

而修改 d 的时候,因为修改了原数组,所以 c 也会对应变成 [1,2,3,4]

小伙伴们想了解更多,可以搜索 JS 深拷贝与浅拷贝

划重点:简单来说,有两个对象 A 和 B,B = A,当你修改 A 时,B 的值也跟着发生了变化,这时候就叫浅拷贝。如果不发生变化,就叫深拷贝。

所以,如果和猜测的一样,那么 [4,1,8,4,5][5,0,1,8,4,5] 需要判断的,是它们在某个位置开始是否在同一地址。

不清楚 C、C++、 Java 等编程语言是否可行,但是在 JS 中,这样的数据,即:

  • 原始数据: [8,4,5]

  • 拷贝数据 A: [4,1,8,4,5]

  • 拷贝数据 B: [5,0,1,8,4,5]

那么,它在 JS 中如何表示呢?jsliang 在这里尝试了一下:

  1. let base = {

  2. val: 8, next: {

  3. val: 4, next: {

  4. val: 5, next: null,

  5. },

  6. },

  7. };

  8. let headA = {

  9. val: 4, next: {

  10. val: 1, next: base,

  11. },

  12. };

  13. let headB = {

  14. val: 5, next: {

  15. val: 0, next: {

  16. val: 1, next: base,

  17. },

  18. },

  19. }

接着,我们分析下我们的代码:

  1. let a = headA,

  2. b = headB;

  3. // 相交则返回当前节点,否则返回 null

  4. // 当 a、b 不相交时:

  5. // 1. 如果 a 为 null,将 headB 赋值给 a;

  6. // 2. 如果 b 为 null,将 headA 赋值给 b;

  7. while (a !== b) {

  8. a = a ? a.next : headB;

  9. b = b ? b.next : headA;

  10. }

怎么说呢?我们是不是有两条链表:ab

a 的长度是 5, b 的长度是 6,那么,我们就可以利用这个长度差,做一些羞羞的事:

  1. [4, 1, 8, 4, 5][5, 0, 1, 8, 4, 5]

  2. [5, 0, 1, 8, 4, 5][4, 1, 8, 4, 5]

可以看到的是,遍历一轮后,刚好接触到了一块,从而返回最终结果。

最后,把这个尝试的在本地测试了一下,完全 OK,说明我们假设的数据 OK 了,再配合上面的解题代码,成功完成了这道题的破解。


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

LeetCode - 160 - 相交链表(intersection-of-two-linked-lists)

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

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

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

失控

失控

[美] 凯文·凯利 / 东西文库 / 新星出版社 / 2010-12 / 88.00元

《失控》,全名为《失控:机器、社会与经济的新生物学》(Out of Control: The New Biology of Machines, Social Systems, and the Economic World)。 2006年,《长尾》作者克里斯·安德森在亚马逊网站上这样评价该书: “这可能是90年代最重要的一本书”,并且是“少有的一年比一年卖得好的书”。“尽管书中的一些例子......一起来看看 《失控》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器