17. Split a Circular linked list into two halves

17. Split a Circular linked list into two halves

Problem link :- click here

package Linked_List;

public class LinkedList__17
{
	/*
	 	Given a circular singly linked list of size n, split it into two halves circular linked list.
	 	If there are odd number of nodes in the given linked list then out of the resulting 
	 	two halved linked lists, first list should have one node more than the second list.
	 	The resultant lists should also be circular lists and not linear lists.
	 	
	 	1 -> make the circular linked list to linear linked list
	 	2 -> find the middle node of the linear linked list 
	 	3 -> store the middle and next to middle in a node variable
	 	4 -> make the first and second linear linked list circular
	 */
	
	static void splitCircularListToTwoHalves(LinkedList list, LinkedList list1, LinkedList list2)
	{
		if(list.head == null)
			return;
		
		//step 1 :- 
		Node head = list.head;
		Node temp = list.head;
		while(temp.next != head)
		{
			if(temp.next == null)
				return;
			temp = temp.next;
		}
		//now temp is the last node, therefore make next of that node as null
		temp.next = null;
		
		//step 2 :-
		Node slow = head;
		Node fast = head;
		while(fast.next != null  &&   fast.next.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		
		//step 3 :- 
		Node mid1=null, mid2=null;
		if(fast.next == null)
			mid1 = slow;
		else
			mid1 = slow.next;
		mid2 = mid1.next;
		
		//step 4 :- 
		mid1.next = head;
		
		for(temp=mid2; temp.next!=null; temp=temp.next)
		{}//finding the last node of the second sun-list
		temp.next = mid2;
		
		//step 5 :- 
		list1.head = head;
		list2.head = mid2;
		
		System.out.println("Circular lists after splitting : ");
		printList(list1);
		printList(list2);
	}
	
	static void splitCircularLinkedList(LinkedList list, LinkedList list1, LinkedList list2)
	{
		if(list.head == null)
			return;
		
		Node fast = list.head;
		Node slow = list .head;
		//finding the middle node two pointer approach(hare and tortoise)
		while(fast.next != list.head  &&  fast.next.next != list.head)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		
		//creating list 1 which have nodes up-to 'slow'
		Node node = list.head;
		while(node != slow)
		{
			list1.push(node.data);
			node = node.next;
		}
		list1.push(node.data);
		
		
		//creating list 2 which have nodes starting from 'slow.next' till last node
		node = slow.next;
		while(node != list.head)
		{
			list2.push(node.data);
			node = node.next;
		}
		
		//making list 1 circular
		Node first = list1.head;
		Node end = list1.head;
		while(end.next != null)
        		end = end.next;
		end.next = first;
		
		//making list 2 circular
		first = list2.head;
		end = list2.head;
		while(end.next != null)
        		end = end.next;
		end.next = first;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(5);
		list.push(7);
		
		//making the list circular 
		list.head.next.next.next = list.head;
		
		System.out.println("Circular linked list before splitting : ");
		printList(list);
		
		LinkedList list1 = new LinkedList();
		LinkedList list2 = new LinkedList();
		splitCircularLinkedList(list, list1, list2);
		printList(list1);
		printList(list2);
	}

	static void printList(LinkedList list)
	{
		int n = list.size();
		Node temp=list.head;
		for(int i=0; i<n; i++)
		{
			System.out.print(temp.data + "-> ");
			temp=temp.next;
		}
		System.out.println();
	}
}

Time complexity :- O(n)
Space complexity :- O(1)