JAVA Program to Split Circular Linked List into two halves

February 21, 2023

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.

Deletion in Circular Linked List

Sorted Insert In Circular Linked List

Insertion and Deletion in a Circular Linked List

Count nodes in Circular Linked List

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

Method 1

Method 2

Method 1

Run

import java.util.*;
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.add (50);
      Obj.add (60);

      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)
      {
	head = newNode;
	tail = newNode;
	newNode.next = head;
      }
    else
      {
	tail.next = newNode;
	tail = newNode;
	tail.next = 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;
  }
}

Output

Circular Linked List is
 10 20 30 40 50 60
Circular Linked List is
 10 20 30
Circular Linked List is
 40 50 60

Method 2

Run

import java.lang.*;
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.add (50);
      Obj.add (60);

      System.out.println ("Original List");
      Obj.print ();

      Obj.split ();
      Obj.print (list1);
      Obj.print (list2);

  }
  public class Node
  {
    int element;
    Node next;
    Node prev;

    public Node (int element)
    {
      this.element = element;
    }
  }
  static Node list1, list2;
  public Node head = null;
  public Node tail = null;
  public void print ()
  {
    Node temp = head;
    if (head == null)
      {
	System.out.println ("null");
      }
    else
      {
	do
	  {
	    System.out.print (" " + temp.element);
	    temp = temp.next;
	  }
	while (temp != head);
	System.out.println ();
      }
  }

  public void add (int element)
  {
    Node newNode = new Node (element);
    if (head == null)
      {
	head = newNode;
	tail = newNode;
	newNode.next = head;
	newNode.prev = head;
      }
    else
      {
	tail.next = newNode;
	newNode.prev = tail;
	tail = newNode;
	tail.next = head;
      }
  }
  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 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;
  }
}

Output

Original List
 10 20 30 40 50 60
Circular Linked List is
 10 20 30
Circular Linked List is
 40 50 60

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Circular Linked List

Introduction to Circular Linked List
Click Here
Circular Linked List Applications
Click Here
Circular Linked List in –
C | C++ | Java
Insertion in Circular Linked List –
C | C++ | Java
Insertion at the beginning–
C | C++ | Java
Insertion at the end –
C | C++ | Java
Insertion at nth position –
C | C++ | Java
Deletion in Circular Linked List –
C | C++ | Java
Deletion from beginning in Circular Linked List –
C | C++ | Java
Deletion from nth position in Circular Linked List –
C | C++ | Java
Deletion from end in Circular Linked List –
C | C++ | Java
Insertion and Deletion in Circular Linked List – C | C++ | Java
Split a Circular Linked List in two halves –
C | C++ | Java
Count nodes in Circular Linked List –
C | C++ | Java
Sorted Insert In Circular Linked List –
C | C++ | Java
Insertion in the middle in Circular Linked List –
C | C++ | Java

Circular Linked List

Introduction to Circular Linked List
Circular Linked List Applications
Circular Linked List in – C | C++ | Java
Insertion in Circular Linked List – C | C++ | Java
- Insertion at the beginning– C | C++ | Java
- Insertion at the end – C | C++ | Java
- Insertion at nth position – C | C++ | Java
Deletion in Circular Linked List – C | C++ | Java
- Deletion from beginning in Circular Linked List – C | C++ | Java
- Deletion from nth position in Circular Linked List – C | C++ | Java
- Deletion from end in Circular Linked List – C | C++ | Java
Insertion and Deletion in a Circular Linked List – C | C++ | Java
Split a Circular Linked List in two halves – C | C++ | Java
Count nodes in Circular Linked List – C | C++ | Java
Sorted Insert In Circular Linked List – C | C++ | Java
Insertion in the middle in Circular Linked List – C | C++ | Java