题目描述
题解一(哈希表)
思路
遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环
代码
publicclassSolution{publicListNodedetectCycle(ListNodehead){ListNodepos=head;Set<ListNode>visited=newHashSet<ListNode>();while(pos!=null){if(visited.contains(pos)){returnpos;}else{visited.add(pos);}pos=pos.next;}returnnull;}}复杂度分析
- 时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点
- 空间复杂度：O(N)，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中
题解二(快慢指针)
思路
代码
publicclassSolution{publicListNodedetectCycle(ListNodehead){// 如果链表为空或只有一个节点且无环，直接返回 nullif(head==null||head.next==null){returnnull;}ListNodeslow=head;ListNodefast=head;// 阶段一：快慢指针判断是否有环while(fast!=null&&fast.next!=null){slow=slow.next;// 慢指针走一步fast=fast.next.next;// 快指针走两步// 如果快慢指针相遇，说明有环if(slow==fast){// 阶段二：寻找环的入口ListNodeindex1=fast;// index1 从相遇点开始ListNodeindex2=head;// index2 从头节点开始// 两个指针每次各走一步，直到相遇while(index1!=index2){index1=index1.next;index2=index2.next;}// 相遇点即为环的入口returnindex1;}}// 如果退出循环，说明遇到了 null，链表没有环returnnull;}}复杂度分析
- 时间复杂度：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)
- 空间复杂度：O(1)。我们只使用了 slow,fast,index1,index2四个指针
