title: Splitting a Circular Linked List in to two halves
body: <p>I am dealing with a problem where i am to split a Circular linked list in to two halves. If the list is even then the split would result in to two even lists. If the split is odd the first list would have the extra node.</p>
  
  <p>Following is code for my node class</p>
  
  <pre><code>public class CLLNode {
  
      private int data;
      private CLLNode next;
  
      public CLLNode(int d)
      {
          this.data = d;
      }
  
      public void setData(int d)
      {
          this.data = d;
      }
  
      public int getData()
      {
          return this.data;
      }
  
      public void setNext(CLLNode n)
      {
          this.next = n;
      }
  
      public CLLNode getNext()
      {
          return this.next;
      }
  
  }
  </code></pre>
  
  <p>Following is code for my Circular linked list class</p>
  
  <pre><code>public class CLinkedList {
  
      private CLLNode Head;
  
      public CLinkedList()
      {
          Head = null;
      }
  
      public CLLNode getHead()
      {
          return this.Head;   
      }
  
      public void insertFirst(int d)
      {
          CLLNode n = new CLLNode(d);
          if(Head == null)
          {
              this.Head = n;
              n.setNext(n);
          }
          else
          {
              CLLNode temp = this.Head;
              while(temp.getNext()!= this.Head)
              {
                  temp = temp.getNext();
              }
              n.setNext(this.Head);
              temp.setNext(n);
              this.Head = n;
          }
      }
  
      public void insertLast(int d)
      {
          CLLNode n = new CLLNode(d);
          if(Head == null)
          {
              this.Head = n;
              n.setNext(n);
          }
          else
          {
              CLLNode temp = this.Head;
              while(temp!= null)
              {
                  temp = temp.getNext();
                  if(temp.getNext() == this.Head)
                  {
                      break;
                  }
              }
  
              n.setNext(temp.getNext());
              temp.setNext(n);
          }
  
      }
  
      public void deleteFirst()
      {
          CLLNode temp = this.Head;
          CLLNode temp2 = this.Head;
  
          while(temp2!=null)
          {
              temp2 = temp2.getNext();
              if(temp2.getNext()== this.Head)
              {
                  break;
              }
          }
  
          temp2.setNext(temp.getNext());
          this.Head = temp.getNext();
          temp.setNext(null);
      }
  
      public void deleteLast()
      {
          CLLNode temp = this.Head;
          CLLNode temp2 = this.Head;
  
          while(temp.getNext()!= this.Head)
          {
              temp2 = temp;
              temp = temp.getNext();
          }
  
          temp2.setNext(temp.getNext());
          temp = null;
      }
  
      public void displayList(CLLNode n)
      {
          CLLNode temp = n;
          while(temp!= null)
          {
              System.out.println(temp.getData());
              temp = temp.getNext();
              if(temp == this.Head)
              {
                  break;
              }
          }
      }
  
      public int getLength()
      {
          int count  = 0;
          CLLNode temp = this.Head;
          while(temp != null)
          {
              count ++;
              temp = temp.getNext();
              if(temp == this.Head){
                  break;
                  }
          }
  
          return count;
      }
  
      public void splitList(CLLNode head, CLLNode head1, CLLNode head2)
      {
          CLLNode temp1 = head;
          CLLNode temp2 = head;
          CLLNode temp3 = head;
  
          while(temp2!=null)
          {
              temp1 = temp1.getNext();
              temp2 = temp2.getNext().getNext();
  
              if(temp2.getNext()== head)
              {
                  temp2.setNext(temp1.getNext());
                  head2 = temp1.getNext();
                  temp1.setNext(temp3);
                  head1 = temp3;
                  break;
              }
  
              if(temp2.getNext().getNext()==head)
              {
                  temp2.getNext().setNext(temp1.getNext());
                  head2 = temp2;
                  temp1.setNext(temp3);
                  head1 = temp3;
                  break;
              }
          }
          this.displayList(Head1); // This one goes in to a infinite loop..
          this.displayList(head2);
  
      }
  
  }
  </code></pre>
  
  <p>Following is my main class</p>
  
  <pre><code>public class main {
  
      public static void main(String[] args) {
  
  
  
          CLinkedList list = new CLinkedList();
  
          list.insertLast(10);
          list.insertLast(20);
          list.insertLast(30);
          list.insertLast(40);
  
          CLLNode head = list.getHead();
  
          CLLNode head1 = null;
          CLLNode head2 = null;
  
          list.splitList(head,head1,head2);
  
  
  
      }
  
  }
  </code></pre>
  
  <p>I am able to successfully split the lists i believe but for some reason when i display the newly split list it goes in to a infinite loop. i am not sure why , if someone can please point out my mistake or suggest a fix i would appreciate it. </p>