题目描述 一个链表中包含环，请找出该链表的环的入口结点。

方法一：

思路：借助Collection容器来存储链表元素。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ import java.util.HashMap; public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { HashMap<ListNode, Integer> map = new HashMap<>(); while(pHead != null) { if(!map.containsKey(pHead)) { map.put(pHead, 1); pHead = pHead.next; } else { return pHead; } } return null; } }

---

方法二：

思路： 假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程） 当快慢指针相遇的时候： 此时慢指针走的路程为Sslow = x + m * c + a 快指针走的路程为Sfast = x + n * c + a 2 Sslow = Sfast 2 * ( x + m*c + a ) = (x + n *c + a) 从而可以推导出： x = (n - 2 * m )*c - a = (n - 2 *m -1 )*c + c - a 即环前面的路程 = 数个环的长度（为可能为0） + c - a 什么是c - a？这是相遇点后，环后面部分的路程。（橙色路程） 所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走， 2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x） ，从相遇点开始走的那个指针也一定刚好到达环入口点。 所以2者会相遇，且恰好相遇在环的入口点。

时间复杂度：O(n) 空间复杂度：O(1)

public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode fast = pHead; ListNode slow = pHead; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { break; } } //无环 if(fast == null || fast.next == null) { return null; } //有环 fast = pHead; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }

---

方法三：

思路：方法二有点…难想到了。 当找到环中某个结点时，就可以得到环的长度。 如果链表中环有n个结点，指针P1在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode meetNode = meetNode(pHead); if(meetNode == null) { return null; } int count = 1; ListNode p1 = meetNode.next; while(p1 != meetNode) { count++; p1 = p1.next; } p1 = pHead; for(; count >= 0; count--) { p1 = p1.next; } ListNode p2 = pHead;         while(p1 != p2){             p1 = p1.next;             p2 = p2.next;         }         return p1; } private ListNode meetNode(ListNode pHead) { ListNode fast = pHead; ListNode slow = pHead; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return fast; } } return null; } }