Split a Circular Linked List into two halves

PROBLEM :

Given a Cirular Linked List split it into two halves circular lists. If there are odd number of nodes in the given circular linked list then out of the resulting two halved lists, first list should have one node more than the second list. The resultant lists should also be circular lists and not linear lists.

Input:

You have to complete the method which takes 3 argument: The address of the head of the linked list , addresses of the head of the first and second halved resultant lists.. You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.

Output:

Set the *head1_ref and *head2_ref to first resultant list and second resultant list respectively.


Constraints:

1<=T<=100
2<=N<=100


Example:

Input:
2
3
1 5 7
4
2 6 1 5

Output:
1 5
7
2 6
1 5

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/* The structure of linked list is the following
struct node
{
   int data;
   node* next;
};   */

//  function which splits the circular linked list.  head is pointer
// to head node of given lined list.  head1_ref1 and *head_ref2
// are pointers to head pointers of resultant two halves.

void splitList(struct node *head, struct node **head1_ref,  
                                          struct node **head2_ref)
{
    struct node *temp1,*temp2,*ptr ;
    ptr=(head) ;
   
    temp1=head ;
    temp2=head ;
   
    while(temp2->next!=ptr&&temp2->next->next!=ptr)
    {
        temp1=temp1->next ;
        temp2=temp2->next->next ;
    }
    if(temp2->next==ptr)
    {
        temp2->next=temp1->next ;
        temp1->next=ptr ;
    }
    else if(temp2->next->next==ptr)
    {
        while(temp2->next!=ptr)
            temp2=temp2->next ;
           
        temp2->next=temp1->next ;
        temp1->next=ptr ;
    }
   
        (*head1_ref)=ptr ;
        (*head2_ref)=temp2->next ;
}

---------------------------------------------------------------------------------