A java solution based on divide and conquer (merge Sort)


  • 0
    D
    class Solution {
    
    	public ListNode mergeKLists(ListNode[] lists) {
    		if (lists == null || lists.length == 0)
    			return null;
    		return mergeKLists(lists, 0, lists.length - 1);
    	}
    
    	private ListNode mergeKLists(ListNode[] lists, int left, int right) {
    		if (left < right) {
    			int mid = (left + right) / 2;
    			ListNode leftList = mergeKLists(lists, left, mid);
    			ListNode rightList = mergeKLists(lists, mid + 1, right);
    			return mergeTwoLists(leftList, rightList);
    		}
    		return lists[left];
    	}
    
    	private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		if (l1 == null)
    			return l2;
    		if (l2 == null)
    			return l1;
    		if (l1.val <= l2.val) {
    			l1.next = mergeTwoLists(l1.next, l2);
    			return l1;
    		} else {
    			l2.next = mergeTwoLists(l2.next, l1);
    			return l2;
    		}
    	}
    }
    

Log in to reply
 

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