【题目描述】一个链表中包含环，请找出该链表的环的入口结点。
【解题思路1】 //1.设置两个指针p1和p2，p1每次向前走一步，p2每次向前走两步。若链表中有环，p1和p2会相遇。 //2.头结点到入口处的距离=碰撞点到入口处的距离（这里指前进方向）。 //3.将p1重新放到头结点位置，p2保持在碰撞点位置，同时向前走，再次的碰撞位置即为环的入口。 //4.关于以上的证明如下：
当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则： 2s = s + nr s= nr 设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。 a + x = nr a + x = (n – 1)r +r = (n-1)r + L - a a = (n-1)r + (L – a – x) (L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点=(n-1)循环内环+相遇点到环入口点，当n=1时，得出结论： 》头结点到入口处的距离=碰撞点到入口处的距离（这里指前进方向）//5.关于该系列的扩展，可以参考本博客的另一篇文章–《判断链表中是否有环 —– 有关单链表中环的问题》
public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null || pHead.next==null){ return null; } ListNode p1=pHead, p2=pHead; while(p2!=null && p2.next!=null){ p1=p1.next; p2=p2.next.next; if(p1==p2){ p2=pHead; while(p1 != p2){ p1=p1.next; p2=p2.next; } if(p1==p2){ return p1; } } } return null; } }【解题思路2】 //1.若链表中有环，则一定会有重复的结点出现。并且环的入口结点即为第一个重复的结点。 //2.使用Set来保存遍历到的节点，因为Set集合是不允许出现重复元素的，所以当一个节点被第二次添加的时候，往Set中放元素是失败的。所以可以利用这一点找出第一个重复的元素。
import java.util.HashSet; import java.util.Set; public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { Set<ListNode> set = new HashSet<ListNode>(); while(pHead!= null && set.add(pHead)){ pHead = pHead.next; } return pHead; } }