Split a Circular Linked List into two halves

                         Original Linked List  

                         Result Linked List 1  

                         Result Linked List 2  

// create a function which return a pointer to the middle of the node , then arrange the link between the node of the list to make both the list circular.


// here I do not follow that approach , for fun only
// I take two pointer to the pointer.
// say p1 is slow pointer , p2 is fast pointer.
// when p2==head or p2->link->link==head  , p1 is my middle node.
// rather than return the middle pointer , I update the head1 and head2 pointers to head and (mid+1) by using pass by reference.

// so here there is no need to use pass by reference , since we need only one pointer and that is mid pointer that is pointing to the (middle of the list+1)node , and we can have it by returning that pinter(mid+1) form the function.

// time complexity O(n).   :)

#include<stdio.h>
#include<stdlib.h>


struct node
{
int data;
struct node *link;

};

struct node *createNode(int data)
{
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
p->data=data;
p->link=NULL;

return p;
}

struct node * traverseTillEnd(struct node *head)  // return the last node pointer to the list
{
struct node *p1,*p2=NULL;

if(head==NULL) // return NULL if there is no element in the list
{
return NULL;
}
else if((head->link)==NULL)
{
return head;
}
else
{
p1=head;
p2=p1->link;

while(p2!=head)
{
p1=p1->link;
p2=p2->link;
}

return p1;
}


}


struct node * insertAtEnd(struct node *head,int data)
{

struct node *p=createNode(data);
struct node *temp=NULL;

// traverse till the end of the list. since it is the circular singly linked list, the traversal of ll is litle different.
if(head==NULL)
{
p->link=p;
return p;
}
else
{
temp=(traverseTillEnd(head));
p->link=temp->link;
(temp->link)=p;
}

return head;

}

void printList(struct node *head)
{
struct node *p1=NULL;


if(head==NULL)
{
printf("no element in the list");
}
else
{
p1=head;
printf("-%d-",(p1->data));
p1=p1->link;
while(p1!=head)
{
printf("-%d-",(p1->data));
p1=p1->link;
}
printf("\n");

}

}

void breakListInTwoHalves(struct node *head,struct node **p11,struct node **p22)
{
struct node *p1,*p2,*temp=NULL;
// find the length of the list.
p1=head; // slow pointer
p2=p1->link; // fast pointer

while(p2!=head && (p2->link)!=head)
{
temp=p2;
p1=p1->link;
p2=(p2->link)->link;
//printf("iteration");
}


// setting the values of head1 and head2 of the main

*p22=(p1->link);
*p11=head;



// breaking the list in to two seperate list , so setting the last node link.
if(p2==head)
{
p2=temp->link;  // to point the p2 pointer to the node which is at the end of the list.
}

p2->link=p1->link;
p1->link=head;




}

int main(void)
{

struct node *head=NULL;
head=insertAtEnd(head,5);
head=insertAtEnd(head,3);
head=insertAtEnd(head,6);
head=insertAtEnd(head,1);
head=insertAtEnd(head,7);
head=insertAtEnd(head,10);
head=insertAtEnd(head,15);
//head=insertAtEnd(head,16);
printList(head);

// break the list in two halves ....


struct node *head1,*head2;
breakListInTwoHalves(head,&head1,&head2);


printList(head1);
printList(head2);

//printList(head);

return 0;
}