题目
一个链表中包含环，请找出该链表的环的入口结点。
分析一
这个题目应该有蛮多解法的。第一种是利用hashset,那么hashset有什么特点呢？说道hashset第一反应就应该是不能插入重复的元素。
因此，我们从头开始插入，假如有环的话，插入就会失败，这个时候就是第一个重复的元素，也就是环的开头。
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
import java.util.HashSet;
public class Solution {
HashSet<ListNode> hashSet = new HashSet<>();
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if (pHead == null) {
return null;
}
while(pHead != null){
boolean insertSuccess = hashSet.add(pHead);
if (insertSuccess == false) {
return pHead;
}
pHead = pHead.next;
}
return null;
}
}
分析二
设置两个指针，p1和p2，分别指向链表头，p1每次按照1的步数往前，p2每次按照2的步数向前，当p1和p2相遇的时候，p2比p1多走了k圈。
整个过程如下图所示：（网上的图）
有了这个图就容易分析了
假设AC表示从起点到环入口的距离，CB表示从环入口到相遇点的距离，BC表示相遇点到环入口的位置,CLenght表示环的长度
那么p1走的距离是AC + (m * CLenght) + CB
p2走的距离是：AC + (n*CLenght) + CB
并且2（AC + (m * CLenght) + CB） = AC + (n*CLenght) + CB
那么，AC = （2m-n）CLenght + BC
这就说明，如果将一个指针退回到链表开头，两个指针一起前移，最终会在环入口点相遇。
代码二
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
import java.util.HashSet;
public class Solution {
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) {
p1= pHead;
while ( p1 != p2) {
p1 = p1.next;
p2=p2.next;
}
if (p1 == p2) {
return p1;
}
}
}
return null;
}
}
