腾讯算法测试常见问题：循环链表

给定链表的头节点，返回链表开始进入环的第一个节点。如果链表不包含循环，则返回 null。

示例：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

如果我们在链表中定义循环，我们可以使用快指针和慢指针。快指针的速度是慢指针的两倍。如果两点相交，则说明存在环路。

boolean hasCycle(ListNode head ){

    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null && fast.next!=null){
       fast = fast.next.next;
       slow = slow.next;
       if(fast==slow){
          return true;
       }
    }
    return false;
}

我们可以轻松判断是否存在循环，但是我们如何返回到第一个进入循环的节点呢？我们画个图来分析一下：

假设起点为A，循环入口点为B，快慢指针的交汇点为C，慢速指针到达交汇点在 k 步，从 B 到 C 距离为 m。所以圆环的周长是X。因为指针的速度是2倍。那么我们有：

K-m + X + m = 2K = 快指针走的举例

所以周长 X = K。一旦找到，指针快速前进并到达循环入口点B。精确距离为 X-m = K-m。从起点到节点B的距离也是K-m。因此，快慢指针相遇后，慢指针又回到起点。此时，快、慢指针以相同的速度移动。当它们相遇时，就是循环的入口点。是不是巧合，哈哈哈。

完整代码如下：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head ==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            //快慢指针相等表示有环
            if(slow==fast){
               //回到起点一起相同速度走
               while(head!=fast){
                   head = head.next;
                   fast = fast.next;
               }
               return head;
            }

        }
        return null;
    }
}