最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • LeetCode算法学习之--链表--环形链表II

    正文概述 掘金(坚定)   2021-07-26   43

    大家好今天给大家分享下一道 LeetCode 中间难度 的题目环形链表 II

    题目

    分析

    解法一:Map 法

    思路
    1.路过的节点都记录下来
    2.因为map是从前向后记录的,所以如果有出现访问过的节点
    该节点一定是第入环的第一个节点
    */
    
    var detectCycle = function (head) {
      // 首先排除特殊条件例如: [] 或者 [1]
      if (head === null || head.next === null) {
        return null;
      }
    
      let map = new Map();
      let cur = head;
      while (cur !== null) {
        //如果存在 则一定是第一个节点
        if (map.get(cur)) {
          return map.get(cur);
        }
    
        // 记录每一个节点 从前往后
        map.set(cur, cur);
        cur = cur.next;
      }
    
      return null;
    };
    /* 复杂度
    时间 O(n)
    空间 O(n)
    */
    

    LeetCode算法学习之--链表--环形链表II

    解法二:双指针法

    代码借鉴 leetcode-cn.com/problems/li…

    思路
    假定从头到入口的距离是i步
    从入口到快慢指针重合的位置是j步
    从重合位置再走k步回到重合点
    
    所以 从环内任何一个点出发走(j+k)都会回到原点
    
    1.首先快指针(f)的走的步数一定是 慢指针(s)的两倍
    2.当快指针f与s重合的时候
        1.快指针走的距离是f=a+n(b+c)+b;
        2.慢指针走的距离是s=a+k(b+c)+b;
        3.由于快指针是慢指针距离的2倍 
        所以可以得出 2a+2k(b+c)+2b=a+n(b+c)+b=>  a=-(2k-n+1)(b+c)+c
        4.通过上面的等式我们可以得知,从头走a步的点=== s 从重合点走c步的点,但是a 和c是未知,
        所以我们可以利用重合相撞的办法得到入口点
        5.放一个指针在头部,和s同时走,当相遇的时候就说明到达了环的入口点
    
    */
    var detectCycle = function (head) {
      // 首先排除特殊条件 [] [1]
      if (head === null || head.next === null) {
        return null;
      }
    
      let f = head;
      let s = head;
      while (f !== null && f.next !== null) {
        f = f.next.next; //快指针一次走2步
        s = s.next; //慢指针一次走一步
    
        // 如果相遇说明有环
        if (f === s) {
          // 设置一个指针指向头部
          let extra = head;
          // 当重合相撞的时候就说明到达了环的入口点
          while (extra !== s) {
            //extra一步一步从头开始走
            extra = extra.next;
            // s 从重合点也一步一步走
            s = s.next;
          }
          return s;
        }
      }
    
      return null;
    };
    
    /* 复杂度
    时间 O(n)
    空间 O(1)
    */
    

    LeetCode算法学习之--链表--环形链表II

    总结

    这道题是中等难度的题,Hash很好理解,但是双指针需要多推导。

    大家可以看看我分享的一个专栏(前端搞算法)里面有更多关于算法的题目的分享,希望能够帮到大家,我会尽量保持每天晚上更新,如果喜欢的麻烦帮我点个赞,十分感谢

    文章内容目的在于学习讨论与分享学习算法过程中的心得体会,文中部分素材来源网络,如有侵权,请联系删除,邮箱 182450609@qq.com

    昨天去支持了鸿星尔克和蜜雪冰城,今天又去支持了汇源果汁,哈哈哈,对于良心企业及必须得给他们打打广告。郑州加油!河南加油!中国加油!


    起源地 » LeetCode算法学习之--链表--环形链表II

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元