Day280:给定一个链表，如何判断链表是否有环？

[Genzhen]

// 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
// 如果链表中存在环，则返回 true 。 否则，返回 false 。

---

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案 欢迎大家在下方发表自己的优质见解

二维码加载失败可点击 小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

---

思路分析

其实链表成环的特征非常明显，比如举个现实中的例子。一个人绕着操场跑步，操场就是一个环，如何判断是否跑了一整圈呢，就可以通过打标记的方式，在之前经过点的打上标记，如果再次经过，就证明跑了至少一圈以上了。

同理，链表也可以这样操作，在经过的结点打上标记，如果遍历再次访问到，那证明该链表有环。

编码实现

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = function (head) {
  // 只要结点存在就继续遍历
  while (head) {
    // 如果标记已经打过，那么说明环存在了
    if (head.mark) {
      return true;
    } 
     // 第一次经过，打上标记
      head.mark = true;
      // 继续往下遍历
      head = head.next;
  }
  return false;
};

注意：但是这样会污染链表

其它一些解法

利用数组判断

const hasCycle = function (head) {
  const res = [];
  while (head) {
    if (res.includes(head)) {
      return true;
    }
    res.push(head);
    head = head.next;
  }
  return false;
};

快慢指针

如果快慢指针相遇，则证明有环

const hasCycle = function (head) {
  if (head === null || head.next === null) {
    return false;
  }
  // 定义 slow慢指针，fast快指针
  let slow = head,
    fast = head.next;
  while (slow) {
    if (slow === fast) {
      return true;
    }
    slow = slow?.next || null;
    fast = fast?.next?.next || null;
  }
  return false;
};

JSON.stringify

JSON.stringify方法会自动检测传入的对象是否有环，如果传入的JSON.stringify成功执行，则说明传入的对象一定没有环

const hasCycle = function (head) {
  try {
    JSON.stringify(head);
    return false;
  } catch {
    return true;
  }
};