13. Merge sort for linked list

13. Merge sort for linked list

\

Problem link :- click here

package Linked_List;

public class LinkedList__13
{
	/*
	 	Merge sort
	 	
	 	Here merge sort will be slightly different.
	 	1 -> find the middle node.
	 		using two pointer approach (hare and tortoise)
	 	2 -> mergeSort(left sub list) 
	 	3 -> mergeSort(right sub list)
	 	4 -> merge(left, right)
	 		while merging we will add node by node recursively and return head.
	 */
	
	static Node merge(Node left, Node right)
	{
		if(left == null)
			return right;
		if(right == null)
			return left;
		
		Node result = null;
		
		if(left.data <= right.data)
		{
			result = left;
			result.next = merge(left.next, right);
		}
		else
		{
			result = right;
			result.next = merge(left, right.next);
		}
		
		return result;
	}
	
	static Node mergeSort(Node head)
	{
		if(head == null   ||    head.next == null)
			return head;
		
		Node middle_node = middleNode(head);
		Node next_to_middle = middle_node.next;
		
		//splitting the linked list
		middle_node.next = null;
		
		//sorting the left and right sub list
		Node left = mergeSort(head);
		Node right = mergeSort(next_to_middle);
		
		//merging left and right sub list 
		Node sorted_list = merge(left, right);
		
		return sorted_list;
	}
	
	static Node middleNode(Node head)
	{
		if(head==null)
			return head;
		
		Node slow = head;
		Node fast = head;
		
		while(fast.next != null  &&  fast.next.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		
		return slow;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(15);
		list.push(10);
		list.push(5);
		list.push(20);
		list.push(3);
		list.push(2);
		
		System.out.println("Unsorted linked list : ");
		printList(list);
		
		LinkedList sorted_list = new LinkedList();
		sorted_list.head = mergeSort(list.head);
		
		System.out.println("\nSorted linked list : ");
		printList(sorted_list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n* log(n))
Space complexity :- O(n)