Floyd's cycle detection

Problem Statement: 
                 
 Detect and Remove loop from the given Linked List

After the detection and removal of loop , the linked List will be :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153

/** * Node of a Linked List * @author Prateek * */ class Node{ public Node prev; public int data; public Node next; public Node(int data) { this.prev=null; this.data=data; this.next=null; } } //------------------------------------------------------------------------ /** * Floyd's Cycle detection * Detect and remove loop in a linked List * @author Prateek * */ public class DetectAndRemoveLoop { static Node start; static Node last; static Node temp; static Node currentNode; // before Cycle //null<-14<-13<-9->8<-3<-2<-1 // after cycle is created // <-14<-13<-9->8<-3<-2<-1 // | ^ // |---------------| // public static void main(String[] args) { addNode(1); addNode(2); addNode(3); addNode(8); addNode(9); addNode(13); addNode(14); makeloop(); //display(); detectLoopAndRemoveLoop(); display(); } // Making loop private static void makeloop() { start.next.next.next.next.next.next.next = start.next.next; } /** * Inserting node in the linked list * @param data */ public static void addNode(int data) { Node newNode = new Node(data); if (start == null) { start = newNode; start.next = null; } else { temp = start; while (temp.next != null) { temp = temp.next; } temp.next = newNode; temp = temp.next; temp.next = null; } } // detect loop and call for subroutine for removing the loop private static void detectLoopAndRemoveLoop() { Node slow_ptr=start; Node fast_ptr=start; while(slow_ptr!=null && fast_ptr!=null && fast_ptr.next!=null ) { slow_ptr=slow_ptr.next; fast_ptr=fast_ptr.next.next; if(slow_ptr==fast_ptr) removeLoop(slow_ptr); } } /** * Remove loop Subroutine * @param slow_ptr */ private static void removeLoop(Node slow_ptr) { Node ptr1=slow_ptr; Node ptr2=slow_ptr; // Counter number of nodes in loop int k=1; while(ptr1.next !=ptr2) { ptr1=ptr1.next; k++; } // Fix one pointer to head ptr1=start; ptr2=start; for(int i=0;i<k;i++) { ptr2=ptr2.next; } /* Move both pointers at the same pace, they will meet at loop starting node */ while(ptr2!=ptr1) { ptr1=ptr1.next; ptr2=ptr2.next; } // Get pointer to the last node ptr2=ptr2.next; while(ptr2.next!=ptr1) { ptr2=ptr2.next; } /* Set the next node of the loop ending node to fix the loop */ ptr2=ptr2.next=null; } /** * Display Linked List */ public static void display() { temp = start; while (temp != null) { System.out.println(temp.data); temp = temp.next; } } }