Given a circular linked list, split the list into two halves such that the resultant lists are also circular.
Refer to the example below:
There are two steps to solve this problem:
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).
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);}}
splitList()
method is defined that implements the algorithm above to split a circular linked list into two halves.splitList()
method.Free Resources