Binary Merge Sort (16ms) beats 83.72% java submissions


  • 0
    A

    if your java code just merge the ListNode one by one without priority queue, you may easily get TLE .
    why ? Because I tried it many times (cry) and its complexity is O(n^3).So I have to use the binary merge and it is O(logN * n^2) ---- every merge is O(n^2) and there are logN combination.

    public class Solution {
    
        public ListNode mergeKLists(ListNode[] lists) {
            
        	ListNode result = null;
        	if(lists == null || lists.length < 1)return result;
        	if(lists.length == 1)return lists[0];
        	
        	result = binaryMerge(lists, 0, lists.length-1);
        	return result;
        }
        
       //simple binary merge
        public ListNode binaryMerge(ListNode[] lists, int left, int right){
        	
        	if(lists == null || lists.length <= 0)return null;
        	if(lists.length == 1)return lists[0];
        	if(left == right)return lists[left];
        	
        	if(right - left == 1){
        		return mergeTwoLists(lists[left], lists[right]);
        	}else{
        		int mid = (right + left) / 2;
        		ListNode leftNode = null;
        		ListNode rightNode = null;
        		if(left <= mid)leftNode = binaryMerge(lists, left, mid);
                if(right >= mid+1)rightNode = binaryMerge(lists, mid+1, right);
        		return mergeTwoLists(leftNode, rightNode);
        	}
        }
        
       //merge two list
        public ListNode mergeTwoLists(ListNode list1, ListNode list2){
        	
        	if(list1 == null && list2 == null)return null;
        	if(list1 == null && list2 != null)return list2;
        	if(list1 != null && list2 == null)return list1;
        	
        	ListNode head = null;
        	ListNode resTemp = head;
        	ListNode l1Temp = list1;
        	ListNode l2Temp = list2;
        	
        	while(l1Temp != null && l2Temp != null){
        		
        		if(l1Temp.val >= l2Temp.val){
        			if(resTemp == null){
        				resTemp = l2Temp;
        				head = resTemp;
        				l2Temp = l2Temp.next;
        			}else{
        				resTemp.next = l2Temp;
        				resTemp = l2Temp;
        				l2Temp = l2Temp.next;		
        			}
        		}else{
        			if(resTemp == null){
        				resTemp = l1Temp;
        				head = resTemp;
        				l1Temp = l1Temp.next;
        			}else{
        				resTemp.next = l1Temp;
        				resTemp = l1Temp;
        				l1Temp = l1Temp.next;
        			}
        		}
        	}
        	
        	while(l1Temp != null){
        		resTemp.next = l1Temp;
        		resTemp = l1Temp;
        		l1Temp = l1Temp.next;
        	}
        	
        	while(l2Temp != null){
        		resTemp.next = l2Temp;
        		resTemp = l2Temp;
        		l2Temp = l2Temp.next;
        	}
        	return head;
        }
    }
    

  • 0
    X

    Same idea, but beats 99% java submissions. May be my mergeTwoLists more efficient.

    
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null)
                return null;
            if (lists.length < 2)
                return lists.length == 0 ? null : lists[0];
            int middle = lists.length / 2 - 1;
            return mergeTwoLists(mergeSubLists(lists, 0, middle), mergeSubLists(lists, middle + 1, lists.length - 1));
        }
    
        private ListNode mergeSubLists(ListNode[] lists, int from, int to) {
            if (to == from)
                return lists[from];
            if ((to - from) == 1)
                return mergeTwoLists(lists[from], lists[to]);
            int middle = from + (to - from) / 2;
            return mergeTwoLists(mergeSubLists(lists, from, middle), mergeSubLists(lists, middle + 1, to));
        }
    
        private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null || l2 == null)
                return l1 == null ? l2 : l1;
            ListNode head = null;
            ListNode tail = null;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    if (tail != null)
                        tail.next = l1;
                    else
                        head = l1;
                    tail = l1;
                    l1 = l1.next;
                } else {
                    if (tail != null)
                        tail.next = l2;
                    else
                        head = l2;
                    tail = l2;
                    l2 = l2.next;
                }
            }
            tail.next = l1 == null ? l2 : l1;
            return head;
        }
    
    

Log in to reply
 

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