JAVA Program to Split Circular Linked List into two halves

JAVA Program to Split a Circular Linked List into two halves

JAVA Program to Split a Circular Linked List into two equal halves

To split a circular linked list into two halves all we have to do is make two heads point to two different elements. The first head will be pointing towards the first element like before but the second head will point to the element that will become the first element of the second circular linked list. The references stored in the last nodes will also change for both of the lists. Let’s take a look at the Algorithm and Program for the same.

Steps to be followed to Split a Circular Linked List in to two halves

  • Firstly the number of elements in the circular linked list should be known to us.
  • Divide the linked list using (i+1)/2 value .
  • The first circular linked list will be from first node to (i+1)/2 – 1 position.
  • The second circular linked list will be from (i+1)/2 to the last node.
  • Change the reference of the node of (i+1)/2 – 1 th position to the first element and the first half is done.
  • Make a new header that points at the (i+1)/2 th node, making it the first node of the second circular list. Also, change the reference the last node is pointing towards to the (i+1)/2th node making it the first element of the second circular linked list.
  • In this way, you can split a circular linked list into two halves.

Algorithm

  • split()
  • Node l1 = HEAD
  • Node l2 = HEAD
  • FOR i=0 until  l2.next != head && l2.next.next != head , i++
    • l2 = l2->next->next
    • l1 = l1->next
  • IF l2->next->next == HEAD
    • l2 = l2->next
  • list1 = HEAD
  • IF HEAD->next != HEAD
    • list2 = l1->next
  • l2->next = l1->next;
  •  l1->next = HEAD

JAVA Program to Split A Circular Linked List

public class Main {             
    public static void main(String[] args) {  
        Main Obj = new Main();  
        Obj.add(10); 
        Obj.add(20);  
        Obj.add(30);
        Obj.add(40);  
        Obj.print();  
        Obj.split();
        Obj.print(list1);
        Obj.print(list2);
        } 
    public class Node{  
        int element;  
        Node next; 
        
        public Node(int element) {  
            this.element = element;  
        }  
    } 
    static Node list1, list2;
    public Node head = null;  
    public Node tail = null;
    public void print() {  
        Node current = head;    
        if(head == null) {  
            System.out.println("Empty List");  
        }  
        else {  
            System.out.println("Circular Linked List is");  
            do{     
                //Prints each node by incrementing pointer.  
                System.out.print(" "+ current.element);  
                current = current.next;  
            }while(current != head);  
                        System.out.println();  
                    }  
                }
                public void print(Node head) {  
        Node current = head;    
        if(head == null) {  
            System.out.println("Empty List");  
        }  
        else {  
            System.out.println("Circular Linked List is");  
            do{     
                //Prints each node by incrementing pointer.  
                System.out.print(" "+ current.element);  
                current = current.next;  
            }while(current != head);  
                        System.out.println();  
                    }  
                }
                
    public void add(int element){  
        Node newNode = new Node(element);  
        if(head == null) {   //For a empty list
            head = newNode;  
            tail = newNode;  //For a empty list tail and head both will have the refernce to the new node
            newNode.next = head;  
            }  
        else {  
            tail.next = newNode;  //tail will have the reference to the new node.
            tail = newNode;  //New node will become new tail.
            tail.next = head;  //In circular linked list tail will alaways point to head.
        }  
    }
    public void split() { 
        Node l1 = head; 
        Node l2 = head;
        for (int i=0 ; l2.next != head && l2.next.next != head ; i++) { 
            l2 = l2.next.next; 
            l1 = l1.next; 
        } 
        if (l2.next.next == head) { 
            l2 = l2.next; 
        } 
        list1 = head; 
        
        if (head.next != head) { 
            list2 = l1.next; 
        }
        l2.next = l1.next; 
        l1.next = head; 
    } 
}
Circular Linked List is
10 20 30 40
Circular Linked List is
10 20
Circular Linked List is
30 40