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

剑指offer上的一题,这题有很多方法,但是我们用取巧的一种。
众所周知,如果链表里有环的话,我们遍历时必然会遇到重复的节点,那么我们就可以考虑用一个Set存节点,Set不能存重复的,所以在第一次Set没有存时就是环的入口。

ListNode node=pHead;
        Set<ListNode> s=new LinkedHashSet<ListNode>();
        while(node!=null){//遍历链表
        if(s.add(node)){//如果set里没有此节点,便加入
            node=node.next;
        }else{//当第一次出现set里面已经存在的节点时,就说明是环的入口
            return  node;
        }
        }
        return node;//假如没有环,那么最后一个节点的next便是null

代码参考自:https://blog.csdn.net/ShanXi_wangyu/article/details/100542137
我加了注释

全部评论

相关推荐

03-11 21:46
西北大学 Java
河和静子:这只是实习工资,我学长北大通班博一的,他同学被这家天天发邮件让他去实习,一个月10w
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务