给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出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
我加了注释

全部评论

相关推荐

06-11 13:34
门头沟学院 C++
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
dao_yi:投了1000个左右,回消息的很少,要简历然后说过几天联系的都没有消息了,约面试的基本都是3000左右,足够在当地生活,最后去了一个武汉的3000,干了两天回来考研了,感觉这个行业加班是常态,看能不能考研上岸找个国企,或者大厂。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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