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.

Before split Circular Single linked list After split Circular Single linked list Set A After split Circular Single linked list Set B

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
void insert(struct Node**head1,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=*head1;
    if(*head1==NULL){
      *head1=node;
      node->next=*head1;
    }else{
      struct Node*temp=*head1;
      while(temp->next!=*head1){
        temp=temp->next;
      }
      //Add node at last
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*head1){
  
  if(head1==NULL){
    printf("\n Empty linked list\n");
  }
  else{
    struct Node*temp=head1;
    while(temp){
      printf("  %d",temp->data);
      temp=temp->next;
      if(temp==head1){
        break; //terminate loop
      }
    }

  }
}
//Split linked list
void split(struct Node*head1,struct Node**head2){

  if(head1==NULL){
    printf("\nEmpty Linked List\n");
  }
  else{
    struct Node*temp=head1,*middle=NULL;
    //find middle node
    while(temp!=NULL && 
      temp->next!=head1 && 
      temp->next->next!=head1)
    {
     if(middle!=NULL){
        middle=middle->next;
     }
     else{
      //set second node
      middle=temp->next;
     }
     
      
      temp=temp->next->next;
    }
    if(middle==NULL)
    {
      if(temp->next==head1){
        //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
         *head2=temp->next;
         temp->next->next=*head2;
         temp->next=temp;
      }
    
    }else
    {
      //divide two set of linked list  
      *head2=middle->next;
      middle->next=head1;
      if(temp->next==head1){
        temp->next=*head2;
      }else if(temp->next->next==head1){
        temp->next->next=*head2;
      }

    }
  }

}
int main(){
  //create node pointer
  struct Node*head1=NULL,*head2=NULL;
  //insert element of linked list
  insert(&head1,1);
  insert(&head1,2);
  insert(&head1,3);
  insert(&head1,4);
  insert(&head1,5);
  insert(&head1,6);
  insert(&head1,7);
  insert(&head1,8);
  printf("Original Circular Linked List\n");
  //display all node
  display(head1);
  //split linked list
  split(head1,&head2);
  printf("\nFirst Set of Linked List\n");
  display(head1);
  printf("\nSecond Set of Linked List\n");
  display(head2);

}

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
//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:
  Node *head1,*head2;
  CircularList();
  void insert(int);
  void display(Node *);
  void split();
};
CircularList::CircularList(){
  head1=NULL;
  head2=NULL;
}

//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;
    node->next=head1;
    if(head1==NULL){
      //when linked list empty
      head1=node;
      node->next=head1;
    }else{
      Node*temp=head1;
      //find last node
      while(temp->next!=head1){
        temp=temp->next;
      }
      //Add node at last
      temp->next=node;
    }
  }
}
//display element of Node
void CircularList:: display(Node*head){
  
  if(head==NULL){
    cout<<"Empty linked list";
  }
  else{
   
   struct Node*temp=head;
    while(temp){
      cout<<"  "<<temp->data;
      temp=temp->next;
      if(temp==head){
        break; //terminate loop
      }
    }

  }
}
//Split linked list
void CircularList:: split(){

  if(head1==NULL){
    cout<<"\nEmpty Linked List\n";
  }
  else{
    struct Node*temp=head1,*middle=NULL;
    //find middle node
    while(temp!=NULL && 
      temp->next!=head1 && 
      temp->next->next!=head1)
    {
     if(middle!=NULL){
        middle=middle->next;
     }
     else{
      //set second node
      middle=temp->next;
     }
     
      
      temp=temp->next->next;
    }
    if(middle==NULL)
    {
      if(temp->next==head1){
        //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
         head2=temp->next;
         temp->next->next=head2;
         temp->next=temp;
      }
    
    }else
    {
      //divide two set of linked list  
      head2=middle->next;
      middle->next=head1;
      if(temp->next==head1){
        temp->next=head2;
      }else if(temp->next->next==head1){
        temp->next->next=head2;
      }

    }
  }

}

int main(){
  CircularList obj=CircularList();
  //insert element of linked list
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  cout<<"Original Circular Linked List\n";
  //display all node
  obj.display(obj.head1);
  //split linked list
  obj.split();
  cout<<"\nFirst Set of Linked List\n";
  obj.display(obj.head1);
  cout<<"\nSecond Set of Linked List\n";
  obj.display(obj.head2);
}

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
//Java Program 
//Split a Circular Linked List into two halves
public class LinkedList{
  static class Node{
    int data;
    Node next;
  }
  public static Node head1,head2;
  //Class constructors
  LinkedList(){
    head1=null;
    head2=null;
  } 
  //insert node at last of linke list
  static void insert(int value){
    //Create a node
    Node node=new Node();
    node.data=value;
    node.next=head1;
    if(head1==null){
      head1=node;
      node.next=head1;
    }
    else{
      Node temp=head1;
      //find lase node
      while(temp.next!=head1){
        temp=temp.next;
      }
      //add node
      temp.next=node;
    }
    
  }
  //Display node element of circular linked list
  public static void display(Node head){
    if(head==null){
      System.out.println("Empty Linked List");
    }else{
      
      Node temp=head;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
        if(temp==head) break;
      }
    }
  }


  //Split linked list
  static void  split(){

    if(head1==null){
      System.out.println("\nEmpty Linked List");
    }
    else{
      Node temp=head1;
      Node middle=null;
      //find middle node
      while(temp!=null && 
        temp.next!=head1 && 
        temp.next.next!=head1)
      {
       if(middle!=null){
          middle=middle.next;
       }
       else{
        //set second node
        middle=temp.next;
       }
       
        
        temp=temp.next.next;
      }
      if(middle==null)
      {
        if(temp.next==head1){
          //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
           head2=temp.next;
           temp.next.next=head2;
           temp.next=temp;
        }
      
      }else
      {
        //divide two set of linked list  
        head2=middle.next;
        middle.next=head1;
        if(temp.next==head1){
          temp.next=head2;
        }else if(temp.next.next==head1){
          temp.next.next=head2;
        }

      }
    }

  }

  public static void main(String[] args) {
    LinkedList obj=new LinkedList();
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    System.out.println("Original Circular Linked List");
    //display all node
    obj.display(obj.head1);
    //split linked list
    obj.split();
    System.out.println("\nFirst Set of Linked List");
    obj.display(obj.head1);
    System.out.println("\nSecond Set of Linked List");
    obj.display(obj.head2);
    
  }
}

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
#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
    self.head1=None
    self.head2=None
    
  #Insert new node to End of Linked list  
  def insert(self,data):
    node=Node(data)
    node.next=self.head1
    if(self.head1==None):
        #when no element of linked list
        self.head1=node
        node.next=node
    else:
        temp=self.head1
        while(temp.next!=self.head1):
            temp=temp.next
        #add node    
        temp.next=node    
  #display all element of circular linked list      
  def display(self,head):
    temp=head
    
    while(temp!=None):
      print(temp.data, end=" ")
      temp=temp.next
      #when find first node
      if(temp==head):
        break

    print("\n")

  def split(self):

    if(self.head1==None):
      print("\nEmpty Linked List\n")
    else:
      temp=self.head1
      middle=None
      #find middle node
      while(temp!=None and  
        temp.next!=self.head1 and 
        temp.next.next!=self.head1):
        if(middle!=None):
          middle=middle.next
       
        else:
          #set second node
          middle=temp.next

        temp=temp.next.next
      
      if(middle==None):
        if(temp.next==self.head1):
          #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
          self.head2=temp.next
          temp.next.next=self.head2
          temp.next=temp
        
      
      else:
        #divide two set of linked list  
        self.head2=middle.next
        middle.next=self.head1
        if(temp.next==self.head1):
          temp.next=self.head2
        elif(temp.next.next==self.head1):
          temp.next.next=self.head2
        
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)
  print("Original Circular Linked List")
  #display all node
  obj.display(obj.head1)
  #split linked list
  obj.split()
  print("\nFirst Set of Linked List")
  obj.display(obj.head1)
  print("\nSecond Set of Linked List")
  obj.display(obj.head2)  

if __name__ == '__main__':
  main()

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 

Python : Before Split a Circular linked list Python : after Split a Circular linked list
//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 Node head1,head2;
  public Program(){
    head1=null;
    head2=null;
  }
  //insert node of linked list
  public void insert(int data){
    Node newNode=new Node();
    newNode.data=data;
    newNode.next=head1;
    if(head1==null){
      //when no element of linked list
      head1=newNode;
      newNode.next=head1;
    }
    else{
      Node temp=head1;
      //get last node
      while(temp.next!=head1 ){
        temp=temp.next;
      }
      //add new node
      temp.next=newNode;
    }
  }
  //Display element of linked list
  public void display(Node head){
    if(head==null){
      Console.Write("Empty Linked List");
    }else{
   
      Node temp=head;
      while(temp!=null){
        Console.Write(" {0}",temp.data);
        temp=temp.next;
        //End of Loop iteration 
        if(temp==head) break;
      }
    }
  }
  //Split linked list
  public void  split(){

    if(head1==null){
      Console.Write("\nEmpty Linked List");
    }
    else{
      Node temp=head1;
      Node middle=null;
      //find middle node
      while(temp!=null && 
        temp.next!=head1 && 
        temp.next.next!=head1)
      {
       if(middle!=null){
          middle=middle.next;
       }
       else{
        //set second node
        middle=temp.next;
       }
       
        
        temp=temp.next.next;
      }
      if(middle==null)
      {
        if(temp.next==head1){
          //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
           head2=temp.next;
           temp.next.next=head2;
           temp.next=temp;
        }
      
      }else
      {
        //divide two set of linked list  
        head2=middle.next;
        middle.next=head1;
        if(temp.next==head1){
          temp.next=head2;
        }else if(temp.next.next==head1){
          temp.next.next=head2;
        }

      }
    }

  }


  
  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);
    Console.Write("Original Circular Linked List");
    //display all node
    obj.display(obj.head1);
    //split linked list
    obj.split();
    Console.Write("\nFirst Set of Linked List");
    obj.display(obj.head1);
    Console.Write("\nSecond Set of Linked List");
    obj.display(obj.head2);
    
  }
}

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.

New Comment







© 2021, kalkicode.com, All rights reserved