腾讯常考十道算法真题：环形链表

给定一个链表的头节点head ，返回链表开始入环的第一个节点。如果链表无环，则返回 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;
    }
}