14 Sept 2013

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;
  }
 }
}

No comments:

Post a Comment