Leetcode 环形链表2

使用hasHashSet来解决该问题

是的，使用 HashSet 也是一种常见且简单的解决方法。该方法的思路是通过遍历链表并将每个访问过的节点存储在一个 HashSet 中。当遍历到的某个节点已经存在于 HashSet 中时，说明链表存在环，且这个节点就是环的入口节点。

这种方法的优缺点：

• 优点：

  • 实现简单，逻辑直观。
  • 不需要进行复杂的数学分析。

• 缺点：

  • 空间复杂度是 O(n)，因为需要额外的存储空间来记录已经访问的节点。
  • 时间复杂度依然是 O(n)，因为需要遍历链表中的所有节点。

代码逻辑：

1. 遍历链表：我们使用 current 指针从链表头开始遍历每一个节点。
2. 判断环的入口：在遍历的过程中，检查当前节点是否已经存在于 HashSet 中。如果存在，说明该节点就是链表环的入口节点。
3. 无环处理：如果遍历链表直到 current 为空（即 null），说明链表无环，返回 null。

复杂度分析：

• 时间复杂度：O(n)，因为我们需要遍历链表中的所有节点一次。
• 空间复杂度：O(n)，由于我们使用了一个 HashSet 来存储链表中所有已访问的节点。

对比 Floyd 龟兔赛跑算法：

• Floyd 龟兔赛跑算法的空间复杂度为 O(1)，时间复杂度为 O(n)，因此它在空间复杂度上比使用 HashSet 的方法更优。
• 使用 HashSet 的方法由于需要额外的存储空间，空间复杂度为 O(n)，但它的实现更加直观，不需要快慢指针和数学推导。

总的来说，使用 HashSet 是一种简单易懂的方法，可以解决这个问题，但在空间效率上不如 Floyd 算法。

public class Solution {public ListNode detectCycle(ListNode head) {if(head == null) {return null;}HashSet<ListNode> visited = new HashSet<>();ListNode currentNode = head;while(currentNode != null) {if(visited.contains(currentNode)) {return currentNode;}visited.add(currentNode);currentNode = currentNode.next;}return null;}
}