一个从相遇(有环)时出发,另一个从头结点出发,再次相遇就是入口

链表中环的入口节点

http://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad

先快慢指针,快慢指针相遇则说明有环。

有环后,一个从相遇的地方出发,另一个从head出发,再次相遇就是入口!

大佬的解题:https://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad

    public ListNode detectCycle(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            //相遇了!!则存在环
            if(fast==slow){
                ListNode slow2=head;
                //一个从开始,另一个从相遇开始。如何相遇则是如何看
                while(slow!=slow2){
                    slow=slow.next;
                    slow2=slow2.next;
                }
                return slow;
            }
        }
        return null;

    }
全部评论

相关推荐

点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务