本文共 898 字，大约阅读时间需要 2 分钟。

 思路：快慢指针

1）首先判断是否有环,有环时，返回相遇的节点，无环，返回null

2）有环的情况下，求链表的入环节点。慢指针一次走一个步长，快指针一次走两个步长）第一次相遇的地方为相聚点（证明有环）。

   fast再次从头出发，每次走一步，

   slow从相遇点出发，每次走一步，

   再次相遇即为环入口点。

证明：

快指针与慢指针均从X出发，在Z相遇。此时，慢指针行使距离为a+b，快指针为a+b+n(b+c）。

所以2*(a+b)=a+b+n*(b+c),推出

a=(n-1)*b+n*c=(n-1)(b+c)+c;

得到，将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。

代码：

//环形链表第一个入环节点//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。var detectCycle = function(head) {    if(!head || !head.next)         return null    let slow = head;    let fast = head;    while(fast != null && fast.next != null) {  //while(fast && fast.next) {        slow = slow.next;        fast = fast.next.next;        if(slow == fast) {            fast = head;  // 有环,fast重新回到链表头            while(slow != fast) {  // slow和fast重新相遇时,相遇节点就是入环节点                slow = slow.next;                fast = fast.next;            }            return slow        }    }    return null};

转载地址：http://pnuvi.baihongyu.com/