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