链表环的入环节点

链表中环的入口结点

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;
}
全部评论

相关推荐

头像
04-09 14:29
Java
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务