算法之环形链表1 - 翁先森的博客

141.给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

你能用 O(1)（即，常量）内存解决此问题吗？

解题思路：

1.快慢指针

两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。

用一块一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈。

用一块一慢两个指针遍历链表，如果指针能够相逢，就返回true

遍历结束后，还没有相逢就返回false

1
var hasCycle = function(head) {
2
    let p1 = head;
3
    let p2 = head;
4
    while(p1 && p2 && p2.next) {
5
        p1 = p1.next
6
        p2 = p2.next.next
7
        if(p1 === p2) {
8
            return true;
9
        }
10
    }
11
    return false;
12
};

2.标记法

标记法给遍历过的节点打记号，如果遍历过程中遇到有记号的说明已环🤓

1
const hasCycle = function(head) {
2
  while (head) {
3
    if (head.tag) {
4
      return true;
5
    }
6
    head.tag = true;
7
    head = head.next;
8
  }
9
  return false;
10
};