本文共 830 字，大约阅读时间需要 2 分钟。
题目描述：
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。思路：1.快慢指针；快慢指针一起从起点开始移动，快指针每次移动两步，慢指针每次移动一步；
2.假设起点到入口点长为y，起点到相遇点长为x，所以相遇点距离入口：x-y；环长为r；
3.快慢指针相遇时：快针走的距离 - 慢针走的距离
即2x - x = nr （快针可能比慢针多走n个环长） => x = nr；4.相遇后，快指针从头开始以步长为1与慢指针一起移动；
快针移动到入口的距离：y； 慢针移动的距离：x - y + y = x = nr； 所以当两个指针相遇时，相遇点就是环的入口点。Java实现如下：
public ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHead.next == null) { return null; } ListNode p1 = pHead; ListNode p2 = pHead; while (p2 != null && p2.next != null) { p1 = p1.next; //慢指针一次走一步 p2 = p2.next.next; //快指针一次走两步 if (p1 == p2) { //快慢指针相遇 p2 = pHead; //相遇后，快指针从头开始移动 while (p1 != p2) { //两指针步长都为1 p1 = p1.next; p2 = p2.next; } if (p1 == p2) { //快慢指针再次相遇，相遇点就是环的入口点 return p1; } } } //end while return null; } 转载地址：http://bpdgi.baihongyu.com/