题目描述
一个链表中包含环，请找出该链表的环的入口结点。
解法一：
要想知道环的入口节点，则必须至少经过该节点两次，类似于“字符流中第一个只出现一次的字符”，可以记录之前的节点，每输入一个新节点则判断其出现的次数。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
Set<ListNode> set = new HashSet<ListNode>();
while(pHead != null) {
if(!set.contains(pHead)) {
set.add(pHead);
}
else {
return pHead;
}
pHead = pHead.next;
}
return null;
}
}
解法二：
虽然解法一的时间复杂度为O（n），但是空间复杂度为O（n），考虑是否有办法减少空间复杂度。
这个问题可以分成几部分：
1、判断是否存在环。
可以设置两个指针，慢指针每次只一个节点，快节点每次移动两个节点，则经过若干次循环后，若存在环则快慢节点必有相遇的时刻，否则快指针会首先到达链表尾。
2、判断环中节点数。
当快慢指针相遇时，另快节点保持静止，慢节点继续遍历，当快慢节点再次相遇时，便可知道环中节点数count。
3、利用环中节点数找到换的入口节点。
只需要设置两个慢指针m、n，另n先移动count节点，然后m、n节点同时向前移动，当m和n相遇时，便是在环的入口节点。
时间复杂为O（n），空间复杂度O（1）
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null || pHead.next == null)
return null;
ListNode l1 = pHead;
ListNode l2 = pHead;
int count = 0;
do{
if(l2 == null) {
return null;
}
else {
l1 = l1.next;
l2 = l2.next.next;
}
}while(l1 != l2);
do{
count++;
l1 = l1.next;
}while(l1 != l2);
l1 = pHead;
l2 = pHead;
for(int i = 0; i < count; i++) {
l2 = l2.next;
}
while(l1 != l2) {
l1 = l1.next;
l2 = l2.next;
}
return l1;
}
}
解法三：
image
与解法二相同，我们可以设两个快慢指针m、n，通过两个指针是否相遇来判断是否含有闭环。
但是当m和n相遇时，我们假设相遇点为B，环为顺时针，环总厂为c，环入口点到相遇点的长度为a，起点到环入口点的距离为x，m速度为n的两倍。则相遇时通过的总距离也为两倍：
Sm=2Sn
Sm=x+nc+a
Sn=x+mc+a
所以可以得到x=（n-2m-1）c+c-a
c-a为橙色部分。
所以我们可以令一个指针这时从起点出发，慢指针n继续前进，当两指针相遇时便为环的入口点。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode l1 = pHead;
ListNode l2 = pHead;
int count = 0;
//检查l1和l2是否会相遇
do{
if(l2 == null) {
return null;
}
else {
l1 = l1.next;
l2 = l2.next.next;
}
}while(l1 != l2);
//设置从头出发的指针
l2 = pHead;
while(l1 != l2) {
l1 = l1.next;
l2 = l2.next;
}
return l1;
}
}
解法四：
断链法：
由于题目已经确定了链表中含有环，如果允许对输入进行修改的话，可以将链表逐步断链，最后剩下的节点便为环的入口节点。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead==null|| pHead.next==null) {
return null;
}
ListNode fast=pHead.next;
ListNode slow=pHead;
while(fast!=null){
slow.next=null;
slow=fast;
fast=fast.next;
}
return slow;
}
}
