Given a linked list print if it has a cycle

Given a linked list find if linked list has cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.

Algorithm

1. Initialize a set
2. Put a check if currentNode is already present in set return false (check has to be on the NODE not the value of it)
3. Start with head and add that to SET
4. if you reach end node == null return false

private boolean cycleInALinkedList(Node n) {
        HashSet<Node> set = new HashSet<>();
        Node node = n;
        while (node != null) {
            if(set.contains(node)) {
                return true;
            }
            set.add(node);
            node = node.next;
        }
        return false;
    }

Algorithm2 : Floyd’s Cycle Finding Algorithm

1. Initialize 2 pointers slow and fast, slow is at n , fast moves 2 steps ahead.
2. check till fast != slow if yes return true, if fast or fast.next becomes null, we reached end of the linkedlist and no cycle

    //Floyds algo
    private boolean cycleInALinkedListFloydsAlgo(Node n) {
       Node slow = n;
       Node fast = n.next.next;

       while (fast != null && fast.next != null) {
         if(slow == fast) {
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
       }
       return true;
    }