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

链表中环的入口结点

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点出发,新慢指针从头结点出发,走过的路程相同,相遇点就是目标节点


全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 13:05
点赞 评论 收藏
分享
酷酷我灵儿帅:这去不去和线不线下面说实话没啥关系
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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