题解 | #链表中环的入口结点#

运行时间：14ms
超过75.73% 用Java提交的代码
占用内存：9736KB
超过78.39%用Java提交的代码
public class Solution {

public ListNode EntryNodeOfLoop(ListNode pHead) 
{
    if(pHead==null) return null;
    ListNode l1=pHead;
    ListNode l2=pHead;

//第一个遍历判断是否有环形，有环形则跳出遍历，往下一步走
while(true)
{
l2=l2.next;
if(l2==null) return null;
l2=l2.next;
if(l2==null) return null;
l1=l1.next;
if(l1==l2) break;
}
l1=l1.next;
//上面判断是环以后，说明l1l2都在环里，把两者之间断开用y型找那个入口结点，就是从6型剪开那个环变成了Y型
l2.next=null;
ListNode pHead1=l1;
ListNode pHead2=pHead;
l2=pHead;
//现在是Y型的了，从Y的两个头分别遍历求两个长度
int len1=0;
int len2=0;
while(l1!=null)
{
len1++;
l1=l1.next;
}
while(l2!=null)
{
len2++;
l2=l2.next;
}
//然后把两边长度变成一样的，就是长的那个一直next，知道两边长度一样
if(len1>len2)
{
for(int i=1;i<=(len1-len2);i++)
{
pHead1=pHead1.next;
}
}
if(len2>len1)
{
for(int i=1;i<=(len2-len1);i++)
{
pHead2=pHead2.next;
}
}
//Y型两个头长度一样了，就同时遍历，当相同了就到那个入口结点了
while(pHead1!=null)
{
if(pHead1==pHead2) return pHead1;
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return null;
}