剑指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
我加了注释

京公网安备 11010502036488号