LinkedList Cycle - Java Solutions - HastSet vs Floyd Algo


  • 3
    A

    Solution 1: using Floyd's cycle-finding algorithm.

    public boolean hasCycle(ListNode head) {
    
        if (head == null || head.next == null) {
            return false;
        }
    
        ListNode slowPointer = head.next;
        ListNode fastPointer = head.next.next;
    
        while (   (slowPointer != null && fastPointer != null)) {
    
            if (slowPointer == fastPointer) {
                return true;
            }
            slowPointer = slowPointer.next;
    
            if (fastPointer.next != null) {
                fastPointer = fastPointer.next.next;
            } else {
                fastPointer = null;
            }
    
        }
        return false;
    }
    

    Solution 2: using HastSet - It takes extra space but has let iterations.

    public boolean hasCycle(ListNode head) {
    
        if (head == null) {
            return false;
        }
    
        java.util.Set<ListNode> set = new java.util.HashSet<ListNode>();
    
        while (head.next != null) {
            if (set.add(head.next)) {
                head = head.next;
            } else {
                return true;
            }
        }
    
        return false;
    }

  • 0
    H
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.