Split a circular linked list in two halves in C

July 25, 2019

Split a circular linked list in two halves

Circular linked list has also this topic that how to split linked list in two halves,basically in this topic we want to do the linked list should be split in two halves either in odd or even node.

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 .

Implementation In split a circular linked list

So basically we have a circular linked list where we have the six element,so in the answer we should have two list first list should contain be first element then third then fifth then seven and second list should contain second element, fourth element the six.

In the list have element is 11,89,9,29,7,75 total six element in the circular linked list

we will have two variable first will have the first head usually called to the first head of the list and second head which will point to the node of next.

Now we will have two temporary variable first temp or second temp ,so will start the loop from here which is a node first temp of next should point to next which is 9 and second temp of next should point to node of next,

and we will iterate the loop until we will reach the node of null,and after the complete loop, so will skip the loop

Algorithm

First count the number of node in Circular Linked List.
Second, I have to make the List even.
Third, I make the List half. the front is the same size like the rear. Finally, I have to make two circular Linked List.

Code of split a circular linked list

      #include <stdio.h>//headrer files
     #include <stdlib.h>//library files

   struct n {
   int data;
  struct n *next;//create node
};

    struct n *even = NULL;
    struct n *odd = NULL;
    struct n *linked_list = NULL;

//Create linked_list
    void insert(int data) {
// Allocate memory for new n;
    struct n *link = (struct n*) malloc(sizeof(struct n));
    struct n *present;

    link->data = data;
    link->next = NULL;

    if(linked_list == NULL) {
    linked_list = link;
    linked_list->next = link;
   return;
}
   present = linked_list;

   while(present->next != linked_list)
   present = present->next;

  // Insert link at the end of the linked_list
    present->next = link; 
    link->next = linked_list;
}

   void display(struct n *h) {
   struct n *ptr = h;

   printf("[h] =>");
//start from the beginning
  while(ptr->next != h) { 
  printf(" %d =>",ptr->data);
  ptr = ptr->next;
}
   printf(" %d =>",ptr->data);
   printf(" [h]\n");
}

   void split_linked_list()//function for split the linked list {
   int count = 0;
// Allocate memory for new n;
   struct n *linked_list1;
   struct n *link;
   struct n *present;

   linked_list1 = linked_list;

   while(linked_list1->next != linked_list) {
  struct n *link = (struct n*) malloc(sizeof(struct n));

  link->data =linked_list1->data;
  link->next = NULL;

  if(linked_list1->data%2 == 0) {

   if(even == NULL) {
   even = link;
  even->next = link;
  linked_list1 = linked_list1->next;
  continue;
} else {
  present = even;

   while(present->next != even) {
   present = present->next;
}

// Insert link at the end of the linked_list
  present->next = link; 
  link->next = even;
}
  linked_list1 = linked_list1->next;

} else {
   if(odd == NULL) {
   odd = link;
   odd->next = link;
   linked_list1 =linked_list1->next;
   continue;

} else {
   present = odd;
   while(present->next!= odd) {
   present = present->next;
}

// Insert link at the end of the linked_list
   present->next = link; 
   link->next = odd;

}
    linked_list1 = linked_list1->next;
}
}

// Lets handle the last n
  link = (struct n*) malloc(sizeof(struct n));

   link->data = linked_list1->data;
   link->next = NULL;
   if(linked_list1->data%2 == 0) {
  present = even;

  while(present->next != even) {
  present = present->next;
}

// Insert link at the end of the linked_list
   present->next = link; 
   link->next = even;
} else {
   present = odd;

   while(present->next!= odd) {
   present = present->next;
}

// Insert link at the end of the linked_list
    present->next = link; 
   link->next = odd;
}
}

  int main() {
  int i;

  for(i = 1; i <= 10; i++)
  insert(i);

   printf("Complete linked_list: \n");
   display(linked_list);

  split_linked_list();

  printf("\nOdd : ");
  display(odd);

  printf("Even : ");
  display(even);

  return 0;
}