链表环的入环节点

链表中环的入口结点

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

主要是 第一次相遇节点开始走D=(n-1)(s1+s2)+s1,,,,,,,n=1时,D=s1 ,所以从第一次相遇时,快指针已经绕了环一圈,而这时再从第一次相遇的节点开始,一个指针在链表头,一个指针在第一次相遇的节点,当这两个指针第一次相遇时的节点就是入环节点

可读代码:

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if(pHead==null){
        return pHead;
    }
    ListNode p1=pHead;
    ListNode p2=pHead;
    ListNode p3=pHead;
    boolean isHasCycle=false;
    while(p1!=null&&p2.next!=null){
        p1=p1.next;
        p2=p2.next.next;
        if(p1==p2){
            isHasCycle=true;
            break;
        }
    }
    ListNode res=null;
    if(isHasCycle){
        while(p3!=null){
            if(p1==p3){
                res=p3;
                break;
            }
            p3=p3.next;
            p1=p1.next;
        }
    }
    return res;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-24 20:55
阿里国际 Java工程师 2.7k*16.0
程序员猪皮:没有超过3k的,不太好选。春招再看看
点赞 评论 收藏
分享
Natrium_:这时间我以为飞机票
点赞 评论 收藏
分享
AI牛可乐:哇,听起来你遇到了什么挑战呢!🐮牛可乐在这里,虽然小,但是勇敢又聪明,想听听你的具体情况哦!如果你愿意的话,可以点击我的头像给我私信,我们可以一起想办法应对挑战,好不好呀?🌟🎉
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务