I created some Nodes with lastNode pointing head. In removeCycle method Firstly detected the lastNode and then got error, when I try to make lastNode(i,e prev).next = null

public class loopsRemove {
    public static class Node{
        int data;
        Node next;

        public Node(int data){
            this.data = data;
            this.next = null;
        }
    }

    public static Node Head;
    public static Node Tail;
    public static int count =0;

   
    public static int removeCycle(){
        Node slow = Head;
        Node fast = Head;
          boolean Cycle = false;
    

        while(fast !=null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            count  ;
            if(slow == fast){
                Cycle =true;
               break;
            }
        }
        if(Cycle == false){
            return 0;  //No Cycle and come out of function (int type is just to observe where function is returning
        }
        

        slow = Head;
        Node prev=null;  //to track previous of fast
        while(slow != fast){
            prev = fast;
            slow = slow.next;
            fast = fast.next;  //speed is same as slow now
        }
        prev.next =null;  //Making endNode.next to null
        return 1;   //int return is just to check weather my code is returning here or above
    }
 
    public static void main(String[] args) {
        Head = new Node(3); 
        Head.next = new Node(4);
        Head.next.next = new Node(5);
        Head.next.next.next = new Node(6);
        Head.next.next.next.next = Head;  //cycle formed
        System.out.println(removeCycle());

       
        System.out.println(Head.next.next.next.next.data); // null is expected at the last node if removeCycle works correctly
    }
}

Expected output: 1 null

current output : Exception in thread "main" java.lang.NullPointerException: Cannot assign field "next" because "prev" is null at loopsRemove.removeCycle(loopsRemove.java:44) at loopsRemove.main(loopsRemove.java:55)

CodePudding user response：

The first while ends when

        if(slow == fast){
            Cycle =true;
           break;
        }

Then

    slow = Head;

doesnt change anything, in this case (3->4->5->6) slow is already head, slow==fast is still true and the following while is never entered

    Node prev=null;  //to track previous of fast
        while(slow != fast){
             prev = fast;
             slow = slow.next;
             fast = fast.next;  //speed is same as slow now
         }
         prev.next =null;  

meaning that prev is null when you try to assign prev.next.

Also, if the second while is entered it will never end, since the number of nodes between fast and slow never change.

What do you want to do? If you want to remove the reference from the last node to head so that the list is no longer cyclic, something like this should be enough:

    if(Head==null){
        return 0;
    }
    Node node = Head;
    while(node.next!=null && node.next !=Head) {
        node=node.next;
    }
    node.next=null;
    return 1;

CodePudding user response：

Your algorithm works for breaking cycles anywhere, except when the cycle includes the head node.

To solve this you could temporarily prefix a dummy node before the head, use the algorithm on this longer list, and then omit that dummy node again.

The below code is your code except for the lines that reference dummy:

    public static int removeCycle() {
        Node dummy = new Node(0); 
        dummy.next = Head; // Prefix a dummy node before the head node
        Node slow = dummy; // Apply the algorithm on this longer list
        Node fast = dummy;
        boolean Cycle = false;

        while(fast !=null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            count  ;
            if(slow == fast){
                Cycle =true;
               break;
            }
        }
        if(Cycle == false){
            return 0;
        }
        

        slow = dummy;  // Start at the temporary head
        Node prev=null;
        while(slow != fast){
            prev = fast;
            slow = slow.next;
            fast = fast.next;
        }
        prev.next =null;
        return 1;
    }

Note that in your main program you should not try to print the data of a null reference. Just print the next property that is expected to be null:

        System.out.println(Head.next.next.next.next);

Because the dummy node is not referenced by anything else than a local variable, it can be garbage collected after removeCycle returns.