//基于hash索引
public ListNode EntryNodeOfLoop1(ListNode pHead)
{
ListNode next = pHead;
Set<ListNode> set = new HashSet<ListNode>();
ListNode result = null;//可能不存在环
while(next!=null){
if(!set.contains(next)){
set.add(next);
next = next.next;
}else{
result = next;
break;
}
}
return result;
}
//基于快慢指针
public static ListNode EntryNodeOfLoop2(ListNode pHead){
//找到环的大小
int m= 0;
ListNode next = pHead.next;
ListNode fast =pHead;
ListNode low = pHead;
while(next!=null&&next.next!=null){
low = low.next;
fast =next.next;
next = fast.next;
m++;
if(low == fast)
break;
}
if(next==null||next.next==null)//说明没有环
return null;
//找到链表中倒数第m个节点
//快指针先走m步
fast = pHead;
low = pHead;
for(int i = 0 ;i<m; i++){
fast = fast.next;
}
while(fast != low){
fast = fast.next;
low = low.next;
}
return fast;
}
