How to perform a circular split of a linked list

Problem statement

Given a circular linked list, split the list into two halves such that the resultant lists are also circular.

Refer to the example below:

Example 1
1 of 2

Solution

There are two steps to solve this problem:

  1. Find the middle element of the list.
  2. The node from the beginning to the middle element becomes the first half of the list. Make the first half circular.
  3. The node from the middle element to the end of the list becomes the second half of the list. Make the second half circular.

Refer to this Educative Answer to find the middle element of the linked list.

In the code below, the time complexity is O(N) and the space complexity is O(1).

Code

public class Main{
static class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
static class CircularLinkedList{
Node head, firstPartHead, secondPartHead;
public CircularLinkedList() {
this.head = null;
}
public void addFront(int data){
Node node = new Node(data);
if(head == null){
head = node;
node.next = head;
return;
}
Node temp = head;
while(temp.next != head)
temp = temp.next;
node.next = head;
temp.next = node;
}
public void displaySubList(Node thead){
Node temp = thead;
do {
System.out.print(temp.data + " - ");
temp = temp.next;
} while(temp != thead);
System.out.println(thead.data);
}
public void displayList(){
displaySubList(head);
}
public void splitList(){
Node slow = head;
Node fast = head;
if (head == null) {
return;
}
while (fast.next != head
&& fast.next.next != head) {
fast = fast.next.next;
slow = slow.next;
}
if (fast.next.next == head) {
fast = fast.next;
}
firstPartHead = head;
if (head.next != head) {
secondPartHead = slow.next;
}
fast.next = slow.next;
slow.next = head;
}
}
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.addFront(5);
cll.addFront(4);
cll.addFront(3);
cll.addFront(2);
cll.addFront(1);
System.out.println("Original list - ");
cll.displayList();
Node head1 = null, head2 = null;
cll.splitList();
System.out.println("First half - ");
cll.displaySubList(cll.firstPartHead);
System.out.println("Second half - ");
cll.displaySubList(cll.secondPartHead);
}
}

Explanation

  • Lines 47–74: splitList() method is defined that implements the algorithm above to split a circular linked list into two halves.
  • Lines 79-84: A circular linked list is defined.
  • Line 87: The original list is printed.
  • Line 89: The original list is split into half by invoking splitList() method.
  • Line 93: The two halves are printed.

Free Resources

Copyright ©2024 Educative, Inc. All rights reserved