My Java solution using Comparator


  • 0
    J
    public ListNode mergeKLists(List<ListNode> lists) {
    	List<ListNode> nodes = new ArrayList<ListNode>();
    	for (ListNode list : lists) {
    		if (list == null)
    			continue;
    		while (list != null) {
    			nodes.add(list);
    			list = list.next;
    		}
    	}
    	Collections.sort(nodes, new Comparator<ListNode>() {
    		@Override
    		public int compare(ListNode o1, ListNode o2) {
    			return o1.val - o2.val;
    		}
    	});
    	if (nodes.size() <= 0)
    		return null;
    	ListNode cur = nodes.get(0);
    	ListNode head = nodes.get(0);
    	for (int index = 1; index < nodes.size(); index++) {
    		cur.next = nodes.get(index);
    		cur = cur.next;
    	}
    	cur.next = null;
    	return head;
    }

  • 0
    H

    I guess it meant to be solved with O(kn) complexity. Yours is O(knlogkn).


Log in to reply
 

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