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

链表中环的入口结点

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

此题依旧是上道题的变种类型,难度不大,贴出代码和思路以供参考和之后的学习

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (hasCycle(pHead)==false) {
            return null;
        }
        ListNode cur1=pHead;
        ListNode cur2=pHead;
        ListNode cur3=pHead;
        while (cur1.next!=null&&cur1.next!=null) {
            cur1=cur1.next;
            cur2=cur2.next.next;
            if (cur1==cur2) {
                break;
            }
        }
        while (cur1!=cur3) {
            cur1 = cur1.next;
            cur3 = cur3.next;
        }
        return cur1;

    }
    public boolean hasCycle(ListNode head){
        if (head==null){
            return false;}
            ListNode cur1=head;
            ListNode cur2=head;
            while (cur2!=null&&cur2.next!=null){
                cur1=cur1.next;
                cur2=cur2.next.next;
                if (cur1==cur2){
                    return true;
                }
            }
            return false;
    }
}

思路:先确定链表是否有环,运用之前的代码即可,其次,在默认有环的情况下,利用快慢指针法将两个指针在环中第一次碰见的节点记录,并在头结点新建立一个慢指针,和第一个慢指针同时走,当两个指针相遇的节点,就是目标节点

图是如下:

大佬的图解,十分明了,慢指针走了a+b的长度,快指针走了2(a+b),所以算下来a=c,于是当旧慢指针从p点出发,新慢指针从头结点出发,走过的路程相同,相遇点就是目标节点


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
06-07 12:20
新余学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务