/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null || pHead.next == null){ return null; } //第一步 利用快慢指针判断是否有环 ListNode fast = pHead; ListNode slow = pHead; boolean hasLoop = false; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ hasLoop = true; break; } } if(hasLoop){ //第二步 计算环的长度 既然fast 和 slow 已经相遇了 fast在走一圈不就是环的长度吗 int loopLength = 1; fast = fast.next; while(fast != slow){ loopLength ++; fast = fast.next; } //第三步 寻找入口节点 这里我们假设把环展开(环长度已经知道了),让一个指针A提前走一个环的长度 //另一个指针B从头开始走 那么A走到头B刚好走到环节点的前一个位置 A和B再往前走就是环节点了(相遇即是环节点),因为展开是我们假设的 fast = pHead; slow = pHead; //fast 先走一个环长度 for(int i = 0;i < loopLength;i++){ fast = fast.next; } while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; } else { return null; } } }