problem

  • you have to split the circular Linked List with the same size of Divisions.

  • Maybe if circular Linked List is odd, you have to change the number of node, it is even .

  • if I explain to you with drawings. Just refer to the following pictures.(The following pictures is refered to geeksforgeeks

Algorithm

  1. First count the number of node in Circular Linked List // way to split the list is floyd algorithm, it is much better.

  2. Second, I have to make the List even.

  3. Third, I make the List half. the front is the same size like the rear. Finally, I have to make two circular Linked List.

 struct node 
 {
   int data;
   struct node *next;
 };
 
 void SplitList (struct node * head, struct node **head1_ref, struct node **head2_ref) {
      struct node * fastNode = head;
      struct node * slowNode = head;
      
      if (head == NULL)
       return;
      
      while (fastNode -> next != head && fastNode -> next -> next != head) {
          fastNode = fastNode -> next -> next;
          slowNode = slowNode -> next;
      }
      
      if (fastNode -> next -> next == head)
           fastNode = fastNode -> next;
        
      *head1_ref = head;
      
      // be careful about this. 
      if (head -> next != head)
       *head2_ref = slowNode -> next;
      
      fastNode -> next = slowNode -> next;
    
      slowNode -> next = head;
 }