Merged Sort Approach


  • 1
    T

    We can take merged sort approach. This will have complexity of O(K* LogN) where K is number of elements total in N list.

    public class MergeKLinkList {
    
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    
    		ArrayList<SingleLinkedList<Integer>> inputList = MergeKLinkList.GetInput(in);
    		System.out.println(inputList);
    		
    		SingleLinkNode<Integer> node = MergeKLinkList.MergeKSortedLinkedList(inputList, 0, inputList.size() - 1);
    		SingleLinkedList<Integer> result = new SingleLinkedList<>(node);	
    		System.out.println(result);
    		in.close();
    	}
    
    	public static ArrayList<SingleLinkedList<Integer>> GetInput(Scanner in)
    	{
    		int numberOfLists = in.nextInt();
    		int count = 0;
    		ArrayList<SingleLinkedList<Integer>> inputList = new ArrayList<SingleLinkedList<Integer>>();
    		
    		while(count < numberOfLists)
    		{
    			int number = in.nextInt();
    			int innerCount = 0;
    			SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
    			while(innerCount < number)
    			{
    				list.AddNodeAtEnd(in.nextInt());
    				innerCount++;
    			}
    			
    			inputList.add(list);
    			count++;
    		}
    		
    		return inputList;
    	}
    	
    	public static SingleLinkNode<Integer> MergeKSortedLinkedList(ArrayList<SingleLinkedList<Integer>> list, int startIndex, int endIndex)
    	{
    		if (startIndex > endIndex)
    		{
    			return null;
    		}
    		
    		if (startIndex == endIndex)
    		{
    			return list.get(startIndex).head;
    		}
    		
    		if (startIndex + 1 == endIndex)
    		{
    			return MergeTwoList(list.get(startIndex).head, list.get(endIndex).head);
    		}
    		
    		int midIndex = startIndex + (endIndex - startIndex) / 2;
    		SingleLinkNode<Integer> A = MergeKSortedLinkedList(list, startIndex, midIndex);
    		SingleLinkNode<Integer> B = MergeKSortedLinkedList(list, midIndex + 1, endIndex);
    		
    		return MergeTwoList(A, B);
    	}
    	
    	public static SingleLinkNode<Integer> MergeTwoList(SingleLinkNode<Integer> A, SingleLinkNode<Integer> B)
    	{
    		if (A == null)
    		{
    			return B;
    		}
    		
    		if (B == null)
    		{
    			return A;
    		}
    		
    		SingleLinkNode<Integer> result;
    		
    		if ( A.data > B.data)
    		{
    			result = new SingleLinkNode<Integer>(B.data, null);
    			result.next =  MergeTwoList(A, B.next);
    		}
    		else
    		{
    			result = new SingleLinkNode<Integer>(A.data, null);
    			result.next = MergeTwoList(A.next, B);
    		}
    			
    		return result;
    	}	
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.