LinkedList (Remove Cycle)

// Linked List part - 2

// Deceting "Cycle" in Linked List
// Floyd's Cycle finding algorithm
// Slow and Fast approach
public class LinkedList {
    //node class to represent each element in the linked list
    public static class Node {
        //data to store the value of the node
        int data;
        Node next;

        //constructor to initialize the node with
        //given data and next reference as null
        public Node(int data) {
            // assign the given data to the node
            this.data = data;
            //initialize the next reference as null as
            //it is the last node in the list by default
            this.next = null;
        }
    }

    //head and tail pointers to keep track of the
    //first and last node in the list respectively
    public static Node head;
    public static Node tail;
    //size of the linked list to keep track of the number of nodes
    public static int size;

    //method to add a node at the end of the list
    public void addFirst(int data) {
        //step1 = create new node
        Node newNode = new Node(data);
        //increment size
        size++;
        //base case
        //if list is empty, newNode becomes both head and tail
        if (head == null) {
            head = tail = newNode;
            return;
        }
        //step2 - newNode = next = head;
        newNode.next = head;
        //step3 = head = newNode
        head = newNode;
    }

    //method to add a node at the end of the list
    public void addLast(int data) {
        //step1 - create new node
        Node newNode = new Node(data);
        // increment size
        size++;
        //base case
        if (head == null) {
            head = tail = newNode;
            return;
        }
        //step2 - tail.next = newNode;
        tail.next = newNode;
        // step3 - tail = newNode;
        tail = newNode;
    }

    //method to print the elements of the list
    public void print() {
        if (head == null) {
            System.out.println("Linked List is empty.");
            return;
        }
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println(" null");
    }

    //method to add elements in the middle of the list
    public void add(int idx, int data) {
        //base case
        if (idx == 0) {
            addFirst(data);
            return;
        }
        //if the index is greater than the size of the list
        Node newNode = new Node(data);
        //increment size
        size++;
        //find the node at index-1
        Node temp = head;
        int i = 0;
        //find the node at index-1
        while (i < idx - 1) {
            temp = temp.next;
            i++;
        }
        //newNode -> temp -> next
        //i = idx-1; temp -> prev
        newNode.next = temp.next;
        //if the list is empty or the index is greater than the size of the list
        temp.next = newNode;
    }

    //method to detect cycle in list
    //Floyd's Cycle finding algorithm
    //Slow and Fast approach
    public static boolean isCycle() {
        Node slow = head;
        Node fast = head;
        //if the list is empty or the list has only 
        //one node, then there is no cycle
        while(fast != null && fast.next != null) {
            //move the slow pointer by 1 step at a time
            slow = slow.next; // +1
            //move the fast pointer by 2 steps at a time
            fast = fast.next.next; // +2
            //if the two pointers meet at a point, then there is a cycle
            if(slow == fast) {
                return true; //cycle exists
            }
        }
        //if we reach here, then the loop didn't terminate
        return false;//cycle does not exist
    }

    //method to remove cycle from the list
    public static void removeCycle() {
        //detect cycles
        Node slow = head;
        Node fast = head;
        //if the list is empty or the list has only
        boolean cycle = false;
        //if the list is empty or the list has only
        //one node, then there is no cycle
        while(fast != null && fast.next != null) {
            //move the slow pointer by 1 step at a time
            slow = slow.next;
            //move the fast pointer by 2 steps at a time
            fast = fast.next.next;
            //if the two pointers meet at a point
            //then there is a cycle
            if(fast == slow) {
                //break the cycle
                cycle = true;
                break;
            }
            //if no cycle, return
            if(cycle == false) {
                return;
            }
        }

        //find meeting point
        //if no cycle, return
        slow = head;
        Node prev = null;//last Node
        while(slow != fast) {
            //move prev pointer to the last node of cycle
            prev = fast;
            //move slow pointer one step ahead
            slow = slow.next;
            //move fast pointer one step ahead
            fast = fast.next;
        }

        //break the cycle
        //remove cycle -> last.next = null;
        prev.next = null;
    }
    //main method
    public static void main(String[] args) {
        //creating a Linked List
        head = new Node(1);
        Node temp = new Node(2);
        head.next = temp;
        head.next.next = new Node(3);
        head.next.next.next = temp;
        // head.next.next.next = head;
        //1->2->3->2
        System.out.println(isCycle());
        //remove cycle
        removeCycle();
        //1->2->3
        System.out.println(isCycle());
    }
}