2 simple Java solutions based merge sort idea


  • 0

    For those who doesn't know about bottom-up merge sort, see this tutor link
    http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/merge-sort5.html

    For Bottom-up iterative merge sort solution, I use a queue to maintain the merged result. It takes log(ListNode[].length) times to finish the merging part. Total it takes n*log(ListNode[].length) where n is the total number of nodes of ListNode[]
    This solution can be done in parallel when dealing with massive list nodes , the Queue will be Queue<Future<ListNode>> to hold the feedback from ExecutorService.submit(callable), where callable is the Java Callable class caliing mergeTwoLists(ListNode l1, ListNode l2)

    Another solution is just a simple recursive merge sort.

    //17ms solution beats 75%: Bottom-up iterative merge sort
    public ListNode mergeKLists(ListNode[] lists) {
    	Queue<ListNode> listQueue = new LinkedList<ListNode>();
    	for(int i = 0; i< lists.length;i+=2)
    		if(i == lists.length-1) listQueue.add(mergeTwoLists(lists[i],listQueue.poll()));
    		else listQueue.add(mergeTwoLists(lists[i],lists[i+1]));
    	while(listQueue.size()>1) listQueue.add(mergeTwoLists(listQueue.poll(),listQueue.poll()));
    	return listQueue.poll();
    }
    //14ms solution beats 91%: Recursive merge sort
    public ListNode mergeKLists(ListNode[] lists) {
    	return mergesort(lists, 0, lists.length - 1);
    }
    
    public ListNode mergesort(ListNode[] lists, int left, int right) {
    	if (left > right) return null;
    	else if (left == right) return lists[left];
    	else {
    		int mid = (left + right) / 2;
    		ListNode l1 = mergesort(lists, left, mid);
    		ListNode l2 = mergesort(lists, mid + 1, right);
    		return mergeTwoLists(l1, l2);
    	}
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	ListNode dummyhead = new ListNode(0);
    	ListNode current = dummyhead;
    	while (l1 != null && l2 != null) {
    		if (l1.val <= l2.val) {
    			current.next = l1;
    			l1 = l1.next;
    		} else if (l1.val > l2.val) {
    			current.next = l2;
    			l2 = l2.next;
    		}
    		current = current.next;
    	}
    	current.next = l1 != null ? l1 : l2;
    	return dummyhead.next;
    }

Log in to reply
 

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