Leetcode – 环形链表

作者 : 开心源码 本文共979个字,预计阅读时间需要3分钟 发布时间: 2022-05-13 共265人阅读

题目详情

给定一个链表,判断链表中能否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
假如 pos 是 -1,则在该链表中没有环。

示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

测试数据如下

 let l2 = {      val: 1,      next: null,    };    l2.next = {      val: 2,      next: {        val: 3,        next: {          val: 4,          next: l2,        },      },    };

我想到的解法.gif

我有想到递归,但发现结束条件没法弄…

    var hasCycle = function(head) {      if (head === null) {        return false;      }      let arr = [];      while (head !== null) {        if (arr.includes(head)) {          return true;        }        arr.push(head);        head = head.next;      }      return false;    };

没啥好说的,就是多用了些内存,空间复杂度为O(n)

利用快慢指针的解法.gif

var hasCycle = function (head) {    let slow = fast = head    while (slow && fast && fast.next) {        slow = slow.next        fast = fast.next.next        if (slow === fast) {            return true        }    }    return false};

流程如下:
第一次: slow 为 2,fast 为 3
第二次: slow 为 3,fast 为 1 (已经到了入环口)
第三次: slow 为 4,fast 为 3
第四次: slow 为 1,fast 为 1
O(1)的空间复杂度

翻书.gif

送大家一个入口处不在起始节点的测试数据

   let l3 = {      val: 1,    };    let l5 = {      val: 5,    };    l3.next = l5;    l5.next = l3;    let l2 = {      val: 2,      next: {        val: 3,        next: {          val: 4,          next: l3,        },      },    };

来搞事情啊.gif
我在想如何利用数学推导出可行性,有些文章用跑步举例,我觉得不精确。
如何证实肯定会停在同一个地方,而不是超过呢,假如总是超过就陷入死循环了
我自己在本子上推算了半天也没搞明白,看了少量推理的文章也没看懂,看来需要小姐姐当面给我讲一下子,我现在是不行了,感觉智商为0了

还有求入口处的算法…

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Leetcode – 环形链表

发表回复