环形链表 II

原题链接

使用的方法

• HashSet.contains(Object o) 判断传入的对象是否存在于集合中。

解题思路

• 首先，创建一个空的哈希集合 set。
• 然后，遍历链表，对于每个节点，尝试将其添加到集合 set 中。
• 如果添加成功，继续遍历下一个节点。
• 如果添加失败，说明当前节点已经存在于集合中，链表存在环，返回当前节点作为环的入口。
• 如果遍历完整个链表后没有发现任何节点重复，说明链表不存在环，返回 null。

代码实现

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> set = new HashSet<>();
        while(pos != null){
            if(!set.contains(pos))
                set.add(pos);
            else 
                return pos;
            pos = pos.next;
        }
        return null;
    }
}