public class Solution { /* 链表中环的入口: 若链表中包含环,找到环的入口 - 通过遍历到重复元素,找出第一个环元素 - 快慢指针,只要ab相交,就说明存在环,此时n=2n (a+b = a+b+(b+c)*m) 法一:哈希表法,每遍历一个就放到哈希表中,直到遇到重复元素 法二:快慢指针 1.快慢指针找到相交点 - 2(a+b) = a+b+(b+c)*m - a+b = (b+c)*m --> a = (b+c)*(m-1) + c 2.根据公式找到入环点 b为当前位置,c为环的剩余节点, - 当m为1时(只多转一圈就遇到了) - 当m为n时,多转n圈后,走c步遇到 */ public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null) return pHead; ListNode slow = pHead; ListNode fast = pHead; boolean isLoop = false; //快慢指针判断 是否成环 while(slow.next!=null && fast.next.next!=null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ isLoop = true; break; } } //找到环的入口 2(a+b) = a+b+(b+c)*n -->a=c +(b+c)*(n-1) if(isLoop){ //环的当前位置为b,c为剩余路径 while(pHead != slow){ pHead = pHead.next; slow = slow.next; } return slow; }else{ return null; } } }