Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

The following uses a hash set to track the nodes that has already been visited. The space complexity is O(n), where n is the number of nodes in the list.

public class Solution {
    public ListNode detectCycle(ListNode head) {  
        if (head == null) return null;
        HashSet<ListNode> visited = new HashSet<>();
        for (ListNode node = head; node != null; node = {
            if (visited.contains(node))
                return node;
        return null;
public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val; = null;