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

大家好今天给大家分享下一道 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-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)
*/

总结

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

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

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

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