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

链表中环的入口结点

http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

运行时间: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;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 22:26
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议