| 4 | { |
| 5 | //Function to remove a loop in the linked list. |
| 6 | public static void removeLoop(Node head){ |
| 7 | // code here |
| 8 | // remove the loop without losing any nodes |
| 9 | |
| 10 | //Slow fast Pointers Approach |
| 11 | Node slow = head; |
| 12 | Node fast = head; |
| 13 | |
| 14 | while(fast!=null) |
| 15 | { |
| 16 | //moving fast pointer by two nodes and slow pointer by one node |
| 17 | fast = fast.next; |
| 18 | if(fast!=null) |
| 19 | { |
| 20 | fast = fast.next; |
| 21 | slow = slow.next; |
| 22 | } |
| 23 | |
| 24 | //if they met, means loop detected |
| 25 | if(fast==slow) |
| 26 | { |
| 27 | //reassinging head to slow |
| 28 | slow = head; |
| 29 | |
| 30 | //if cycle is present in head pointer itself |
| 31 | |
| 32 | if(fast == slow)//new slow is pointing to head |
| 33 | { |
| 34 | while(fast.next!=slow)fast = fast.next; |
| 35 | } |
| 36 | |
| 37 | //else make fast pointer to revolve around the loop |
| 38 | //make slow pointer to make a move each time towards the cycle |
| 39 | |
| 40 | //if next of both is same(fast is common for both cases) |
| 41 | //make fast's next as null |
| 42 | else |
| 43 | { |
| 44 | while(fast.next!=slow.next) |
| 45 | { |
| 46 | fast = fast.next; |
| 47 | slow = slow.next; |
| 48 | } |
| 49 | } |
| 50 | fast.next = null; |
| 51 | } |
| 52 | |
| 53 | //Time Complexity : o(n) |
| 54 | //Space Complexity : o(1) |
| 55 | } |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | //GeeksforGeeks driver Code |