LeetCode 141.环形链表
??Blog :《LeetCode 141.环形链表 – JavaScript》
题目形容:给定一个链表,判断链表中能否有环。
解法 1:Floyd 判圈算法
Floyd 判圈算法相似龟兔赛跑,需要用到快指针 fast 和慢指针 slow。算法流程是:
- slow 每次移动 1 不,fast 移动 2 步
- 一直移动下去,若 slow、fast 相遇,那么必有环;若 slow 或者 fast 抵达边界,那么不存在环。
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/linked-list-cycle/// 原文地址:https://xxoo521.com/2020-03-03-linked-list-cycle//** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) { let slow = head; let fast = head; while (slow && fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false;};解法 2: 哈希表
这种解法比较容易想到,使用哈希表来记录节点能否出现过。若存在环,那么一直向下访问,肯定会回到环的入口处。
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/linked-list-cycle/// 原文地址:https://xxoo521.com/2020-03-03-linked-list-cycle//** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) { if (!head) return false; const map = new Map(); let node = head; map.set(node, true); while (node.next) { if (map.get(node.next)) { // map.clear() // 节省时间可以去掉 return true; } map.set(node.next, true); node = node.next; } // map.clear() return false;};更多资料
若有纰漏,欢迎指正。若对您有帮助,请给个「关注+点赞」,您的支持是我升级的动力 ??
- ??Blog:剑指 Offer + Leetcode 题解
- ??Github : dongyuanxin/blog
- ?? 公众号:心谭博客
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode 141.环形链表
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode 141.环形链表