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