29. Merge k sorted linked lists

29. Merge k sorted linked lists

Problem link :- click here

package Linked_List;

public class LinkedList__29
{
	/*
	 	Given K sorted linked list of different sizes. The task is to merge them in such 
	 	a way that after merging they will be a single sorted linked list.
	 				1-> 2-> 3-> 
	 				4-> 5-> 
	 				5-> 6-> 
	 				7-> 8->
	 		output : 	1->  2->  3->  4->  5->  5->  6->  7->  8-> 
	 		
	 	Lets merge 2 linked lists one time 
	 	and their result will be merged with the next linked list
	 */
	
	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 mergeKSortedLinkedList(Node arr[], int k)
	{
		Node result = arr[0];
		for(int i=1; i<k; i++)
			result = merge(result, arr[i]);
		
		return result;
	}
	
	public static void main(String[] args)
	{
		LinkedList list1 = new LinkedList();
		list1.push(1);
		list1.push(2);
		list1.push(3);
		
		LinkedList list2 = new LinkedList();
		list2.push(4);
		list2.push(5);
		
		LinkedList list3 = new LinkedList();
		list3.push(5);
		list3.push(6);
		
		LinkedList list4 = new LinkedList();
		list4.push(7);
		list4.push(8);
		
		System.out.println("Linked lists : ");
		printList(list1);
		printList(list2);
		printList(list3);
		printList(list4);
		
		int k = 4;
		Node arr[] = { list1.head, list2.head, list3.head, list4.head };
		
		LinkedList ans = new LinkedList();
		ans.head = mergeKSortedLinkedList(arr, k);
		System.out.println("\nMerged Linked list : ");
		printList(ans);
	}

	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 * k*log(k))
Space complexity :- O(k)