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

142.给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

**说明：**不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

解法：

1.哈希表

1
var detectCycle = function(head) {
2
  //建立一个Set，如果有重复的，就说明是环。
3
  const memo = new Set()
4

5
  while(head){
6
    if(memo.has(head)){
7
      return head
8
    }else{
9
      memo.add(head)
10
    }
11
    head = head.next
12
  }
13

14
  return null;
15
};

2.快慢指针

1
var detectCycle = function(head) {
2
  let fast = head, slow = head;
3

4
  do{
5
    //检查是否有环 + 寻找相遇点 encounter point
6
    if(!fast || !fast.next) return null;
7
    fast = fast.next.next
8
    slow = slow.next
9
  }while(fast != slow)
10

11

12
  fast = head;
13

14
  //寻找入口 entrance
15
  //为什么这能寻找入口，请看下图
16
  while(fast != slow){
17
    fast = fast.next
18
    slow = slow.next
19
  }
20

21
  return fast;
22
};

复杂度分析时间复杂度：O(N) 空间复杂度：O(1) 有一个快指针fast，慢指针slow；快指针一次走两步，慢指针一次走一步；在有环的情况下，他们俩会在encounter相遇。相遇的时候有(Nfast - 2Nslow) * L = Path + E 通过Lucifer的例子，我们得知(Nfast - 2Nslow) 只要是个整数，就不会影响encounter在环上的位置，所以我们能推导出: Path = L - E (就是那俩蓝色的地方) 这时候fast再从head开始走，slow从encounter走，他们俩每个都走一步，遇见的时候就刚好在环的入口。