牛客网——链表中环的入口节点

矫情吗；* 2022-04-22 13:48 199阅读 0赞

题目描述
    给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

暂时想不到怎么用一步两步的指针出来，就直接暴力

public ListNode EntryNodeOfLoop(ListNode pHead){ 
            HashSet<ListNode> set=new HashSet<>();
            ListNode p=pHead;
            while (p!=null){ 
                if(!set.contains(p)){ 
                    set.add(p);
                }else { 
                    return p;
                }
                p=p.next;
            }
            return null;
        }

正确的做法

public class Solution { 
     
        public ListNode EntryNodeOfLoop(ListNode pHead)
        { 
             if(pHead==null||pHead.next==null)return null;
             ListNode p1=pHead;
             ListNode p2=pHead;
            while(p2!=null&&p2.next!=null)
             { 
                p1=p1.next;
                p2=p2.next.next;
                if(p1==p2)
                { 
                    p1=pHead;
                    while(p1!=p2)
                    { 
                        p1=p1.next;
                        p2=p2.next;
                    }
                    if(p1==p2)return p1;
                }
            }
            return null;
        }
    }

恍然大悟，都走了一半，然后在让两个指针相同速度走就回到入口点

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客-链表中环的入口节点(Java)

链表中环的入口节点【题目描述】对于一个给定的链表，返回环的入口节点，如果没有环，返回null 【思路】 1. 首先判断有没有环我们可以设置两个指针

待我称王封你为后i/ 2023年10月04日 12:59/ 0 赞/ 21 阅读

相关牛客网-删除链表中重复的节点

题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1

Myth丶恋晨/ 2023年03月01日 10:14/ 0 赞/ 14 阅读

相关链表返回环的入口节点

题目描述对于一个给定的链表，返回环的入口节点，如果没有环，返回null 拓展：你能给出不利用额外空间的解法么？说明：本题目包含复杂数据结构ListNode，

矫情吗；*/ 2022年12月21日 04:43/ 0 赞/ 141 阅读

相关链表中环的入口节点

链表中环的入口节点 1、参考资料 https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425a

Dear 丶/ 2022年12月05日 00:56/ 0 赞/ 174 阅读

相关链表中环的入口节点

[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&rp=1&ru=%2Ft

柔光的暖阳◎/ 2022年11月30日 04:20/ 0 赞/ 171 阅读

相关链表中环的入口结点 (C++牛客网)

/ struct ListNode { int val; struct ListNode next; ListN

阳光穿透心脏的1/2处/ 2022年09月10日 10:15/ 0 赞/ 163 阅读

相关链表问题_链表中环的入口节点

题目：一个链表中包含环路，求链表的入口节点。分析：根据求[链表中倒数第K个节点][K]的方法，这个问题可以分为两个步骤：1、判断链表中的节点个数记为K，对于这个可以采用一

矫情吗；*/ 2022年05月21日 07:23/ 0 赞/ 213 阅读

相关链表中环的入口节点

问题描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。有环链表类似于下图中的链表： ![70][] 可以看到该链表中有一个环，其中橙

缺乏、安全感/ 2022年05月14日 03:56/ 0 赞/ 186 阅读

相关牛客网——链表中环的入口节点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。暂时想不到怎么用一步两步的指针出来，就直接暴力 public

矫情吗；*/ 2022年04月22日 13:48/ 0 赞/ 200 阅读

相关【题23 链表中环的入口节点】

【题23 链表中环的入口节点】【题目】如果一个链表中包含环，如何找出环的入口节点？例如：如图的链表中，环的入口节点是节点3 分析： 1. 如何确定

冷不防/ 2022年03月25日 03:14/ 0 赞/ 188 阅读