前言

保持快慢指针对环形链表的敏感性，快慢指针的相遇情况可以判断是否有环存在。但是认识不能止步于此，快慢指针相遇的点，说明了头节点到该点的距离==该点再走到该点的距离，比较快慢在距离的体现上就是一个2倍关系。

一、环形链表

二、快慢指针的两点知识

package com.xhu.offer.everyday;//环形链表2
public class DetectCycle {/*1-找到是否有环？2-如果有环，该如何寻找到入环点？1-快慢指针，如果能相遇，则一定有环；否则无环。2-快慢指针的行为-相遇型-特征：头节点 到 相遇节点 的 距离 == 相遇节点 再到 相遇节点的 距离，比较快慢指针 就是 体现了二倍关系。那么入环节点到相遇节点是固定的，而从头节点和相遇节点再走到相遇节点，都要经过这一条路径，且两距离相等，那么它们俩势必在入口节点相遇。*/public ListNode detectCycle(ListNode head) {//寻找相遇节点ListNode slow = head, fast = slow;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) break;}//1-无环情况if (fast == null || fast.next == null) return null;//2-有环情况，开始寻找公共入口节点。注：根据快慢指针走的距离有二倍特性来解题。slow = head;//从head 出发while (slow != fast) {slow = slow.next;fast = fast.next;}//返回公共路径的第一个节点，也就是入环节点。return fast;}// Definition for singly-linked list.class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}}

总结

1）保持快慢指针对环形链表的敏感性
2）不能停留在快慢指针判断环的基础上，还要分析快慢指针的特点，加以利用，才能将代码简洁，也尽可能减少运行时间。

参考文献

[1] LeetCode 环形链表II