LeetCode 141.环形链表

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

??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.环形链表

发表回复