Linked List: Split circular Linked List into two halves

Problem Statement:

You are given an circular LL, you need to convert into 2 halves.

Example

Input:

-> 1 -> 2 -> 3 -> 4
   ^              |
   | _  _  _  _  _|

Output:

-> 1 -> 2 
   ^    |
   | _ _|

-> 3 -> 4
   ^    |
   | _  |

Solution

We store the mid and last pointers of circular linked list using 2 pointers method

Then make the second half circular LL

Then first half circular LL

Then set the head pointers of two LL

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Node  
{  
    public: 
    int data;  
    Node *next;  
};  

void split_circular_list(Node *head, Node **head1_ref, 
                           Node **head2_ref)  
{  
    Node *slow_ptr = head;  
    Node *fast_ptr = head;  
      
    if(head == NULL)  
        return;  

    while(fast_ptr->next != head &&  
          fast_ptr->next->next != head)  
    {  
        fast_ptr = fast_ptr->next->next;  
        slow_ptr = slow_ptr->next;  
    }  
      
    if(fast_ptr->next->next == head)  
        fast_ptr = fast_ptr->next;  
          
    *head1_ref = head;  
          
    if(head->next != head)  
        *head2_ref = slow_ptr->next;  
          
    fast_ptr->next = slow_ptr->next;  
          
    slow_ptr->next = head;  
}  

void push(Node **head_ref, int data)  
{  
    Node *ptr1 = new Node(); 
    Node *temp = *head_ref;  
    ptr1->data = data;  
    ptr1->next = *head_ref;  
          

    if(*head_ref != NULL)  
    {  
        while(temp->next != *head_ref)  
        temp = temp->next;      
        temp->next = ptr1;  
    }  
    else
        ptr1->next = ptr1; 
      
    *head_ref = ptr1;  
}  

void print_list(Node *head)  
{  
    Node *temp = head;  
    if(head != NULL)  
    {  
        cout << endl;  
        do {  
        cout << temp->data << " ";  
        temp = temp->next;  
        } while(temp != head);  
    }  
} 
  
int main()  
{  
    int list_size, i;  
          
    Node *head = NULL;  
    Node *head1 = NULL;  
    Node *head2 = NULL;  
      
    /* Created linked list will be 1->5->2->8 */
    push(&head, 1);  
    push(&head, 5);  
    push(&head, 2);  
    push(&head, 8);  
      
    cout << "Original Circular Linked List";  
    print_list(head);      
      
    split_circular_list(head, &head1, &head2);  
      
    cout << "\nFirst Circular Linked List";  
    print_list(head1);  
      
    cout << "\nSecond Circular Linked List";  
    print_list(head2); 

    return 0;  
}

Output:

Original Circular Linked List
8 2 5 1
First Circular Linked List
8 2
Second Circular Linked List
5 1