Share my java solution, 84.15%


  • 0
    W
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        return mergeHalf(lists, 0, len);
    }
    
    private ListNode mergeHalf(ListNode[] lists, int start, int end) {
        int len = end - start;
        if(len < 1) return null;
        else if(len < 2) return lists[start];
        else if(len == 2) return mergeTwoLists(lists[start], lists[start+1]);
        else return mergeTwoLists(mergeHalf(lists,start, start + len/2), mergeHalf(lists, start + len/2, end));
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode start = new ListNode(0);
        ListNode tmp = start;
        while(l1 != null && l2 != null) {
            tmp.next = l1.val < l2.val ? l1 : l2;
            if(l1.val < l2.val) l1 = l1.next;
            else l2 = l2.next;
            tmp = tmp.next;
        }
        tmp.next = l1 == null ? l2 : l1;
        return start.next;
    }

Log in to reply
 

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