# Split a Circular Linked List into two halves

Splitting of a circular linked list into two parts. When linked list contains Even numbers of nodes. Then resulted of this, there are divided into two equal parts. head1 is contain first half nodes. And head2 contains second half nodes.

When linked list contain Odd numbers of nodes. Then head1 are containing of the one extra nodes. For example lets linked list contain 7 nodes in this situation first list contain 4 starting nodes and second list contain 3 last nodes pair.

Suppose we are inserted the following (1,2,3,4,5,6,7,8) node in a sequence.

Here given code implementation process.

``````//C Program
//Split a Circular Linked List into two halves
#include<stdio.h>
#include <stdlib.h> //for malloc function

//Create structure
struct Node{
int data;
struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element at end of linked list
//Create dynamic node
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL){
printf("Memory overflow\n");
}else{
node->data=value;
}else{
temp=temp->next;
}
temp->next=node;
}
}
}
//Display element of Node

}
else{
while(temp){
printf("  %d",temp->data);
temp=temp->next;
break; //terminate loop
}
}

}
}

}
else{
//find middle node
while(temp!=NULL &&
{
if(middle!=NULL){
middle=middle->next;
}
else{
//set second node
middle=temp->next;
}

temp=temp->next->next;
}
if(middle==NULL)
{
//only one nodes
//then no need to modification
//less then three node
printf("\n Only one node\n");
}
else{
//when only two nodes of linked list
temp->next=temp;
}

}else
{
//divide two set of linked list
}

}
}

}
int main(){
//create node pointer
//display all node

}``````

#### Output

``````Original Circular Linked List
1  2  3  4  5  6  7  8
1  2  3  4
5  6  7  8``````
``````//C++ Program
//Split a Circular Linked List into two halves
#include<iostream>
using namespace std;

//create structure
struct Node{
int data;
struct Node*next;
};
class CircularList{

public:
CircularList();
void insert(int);
void display(Node *);
void split();
};
CircularList::CircularList(){
}

//insert Node at end of linked list
void CircularList:: insert(int value){
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow"<<endl;
}else{
node->data=value;
}else{
//find last node
temp=temp->next;
}
temp->next=node;
}
}
}
//display element of Node

}
else{

while(temp){
cout<<"  "<<temp->data;
temp=temp->next;
break; //terminate loop
}
}

}
}
void CircularList:: split(){

}
else{
//find middle node
while(temp!=NULL &&
{
if(middle!=NULL){
middle=middle->next;
}
else{
//set second node
middle=temp->next;
}

temp=temp->next->next;
}
if(middle==NULL)
{
//only one nodes
//then no need to modification
//less then three node
cout<<"\n Only one node\n";
}
else{
//when only two nodes of linked list
temp->next=temp;
}

}else
{
//divide two set of linked list
}

}
}

}

int main(){
CircularList obj=CircularList();
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(4);
obj.insert(5);
obj.insert(6);
obj.insert(7);
obj.insert(8);
//display all node
obj.split();
}``````

#### Output

``````Original Circular Linked List
1  2  3  4  5  6  7  8
1  2  3  4
5  6  7  8``````
``````//Java Program
//Split a Circular Linked List into two halves
static class Node{
int data;
Node next;
}
//Class constructors
}
//insert node at last of linke list
static void insert(int value){
//Create a node
Node node=new Node();
node.data=value;
}
else{
//find lase node
temp=temp.next;
}
temp.next=node;
}

}
//Display node element of circular linked list
}else{

while(temp!=null){
System.out.print("  "+temp.data);
temp=temp.next;
}
}
}

static void  split(){

}
else{
Node middle=null;
//find middle node
while(temp!=null &&
{
if(middle!=null){
middle=middle.next;
}
else{
//set second node
middle=temp.next;
}

temp=temp.next.next;
}
if(middle==null)
{
//only one nodes
//then no need to modification
//less then three node
System.out.println("\n Only one node");
}
else{
//when only two nodes of linked list
temp.next=temp;
}

}else
{
//divide two set of linked list
}

}
}

}

public static void main(String[] args) {
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(4);
obj.insert(5);
obj.insert(6);
obj.insert(7);
obj.insert(8);
//display all node
obj.split();

}
}``````

#### Output

``````Original Circular Linked List
1  2  3  4  5  6  7  8
1  2  3  4
5  6  7  8``````
``````#Python Program
#Split a Circular Linked List into two halves
class Node:
def __init__(self,data):
self.data=data
self.next=None

#create class CircularList
class CircularList:
def __init__(self):
#Assign default value

#Insert new node to End of Linked list
def insert(self,data):
node=Node(data)
#when no element of linked list
node.next=node
else:
temp=temp.next
temp.next=node
#display all element of circular linked list

while(temp!=None):
print(temp.data, end=" ")
temp=temp.next
#when find first node
break

print("\n")

def split(self):

else:
middle=None
#find middle node
while(temp!=None and
if(middle!=None):
middle=middle.next

else:
#set second node
middle=temp.next

temp=temp.next.next

if(middle==None):
#only one nodes
#then no need to modification
#less then three node
print("\n Only one node\n")

else:
#when only two nodes of linked list
temp.next=temp

else:
#divide two set of linked list

def main():
#Create Object of class CircularList
obj=CircularList()
#Insert element
obj.insert(1)
obj.insert(2)
obj.insert(3)
obj.insert(4)
obj.insert(5)
obj.insert(6)
obj.insert(7)
obj.insert(8)
#display all node
obj.split()

if __name__ == '__main__':
main()``````

#### Output

``````Original Circular Linked List
1 2 3 4 5 6 7 8

1 2 3 4

5 6 7 8

``````
``````//C# program
//Split a Circular Linked List into two halves
using System;
//node class
public class Node{
public  int data;
public  Node next;
}
class Program
{
public Program(){
}
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
//when no element of linked list
}
else{
//get last node
temp=temp.next;
}
temp.next=newNode;
}
}
}else{

while(temp!=null){
Console.Write(" {0}",temp.data);
temp=temp.next;
//End of Loop iteration
}
}
}
public void  split(){

}
else{
Node middle=null;
//find middle node
while(temp!=null &&
{
if(middle!=null){
middle=middle.next;
}
else{
//set second node
middle=temp.next;
}

temp=temp.next.next;
}
if(middle==null)
{
//only one nodes
//then no need to modification
//less then three node
Console.Write("\n Only one node");
}
else{
//when only two nodes of linked list
temp.next=temp;
}

}else
{
//divide two set of linked list
}

}
}

}

static void Main(){

Program obj=new Program();
//Insert element value
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(4);
obj.insert(5);
obj.insert(6);
obj.insert(7);
obj.insert(8);
//display all node
obj.split();

}
}``````

#### Output

``````Original Circular Linked List 1 2 3 4 5 6 7 8
First Set of Linked List 1 2 3 4
Second Set of Linked List 5 6 7 8``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.