using a min-heap, but too many lines of code, how could I make it shorter? thanks


  • 0

    I used a min-heap.
    k = num of lists.
    n = avg size of each list.
    complexity is "O(nk*log(k))".
    but it's not to my satisfactory since there're too many lines. how could I make it shorter ? thanks

    public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int size = lists.length;
        ListNode head = null;
        ListNode last = null;
        buildHeap(lists, size);
        while(size > 0) {
            ListNode min = lists[0];
            if(head == null) {
                head = min;  // 1st node merged
                last = min;
            } else {
            	last.next = min;
            	last = last.next;
            }
            
            if(min == null) {  // min heap returning max value, coming to end
                break;
            } 
            
            lists[0] = lists[0].next;
            if(lists[0] == null) {
                swap(lists, 0, size - 1);
                size--;
            }
            siftDown(lists, size, 0);
        }
        return head;
    }
    
    public void buildHeap(ListNode[] lists, int size) {
        for(int i = (size - 1) / 2; i >= 0; i--) {
            siftDown(lists, size, i);
        }
    }
    
    //* making a min-heap, taking 'null' as the max value, it's bigger than any node
    public void siftDown(ListNode[] lists, int sizeNonNull, int index) {
    	if(sizeNonNull <= 1) {
    		return;
    	}
        int child = 2 * index + 1;
        while (child < sizeNonNull) {
            if (child + 1 < sizeNonNull 
            && (lists[child] == null 
                || (lists[child + 1] != null
                    && lists[child].val > lists[child + 1].val))) {
                child++;
            }
            
            if(lists[index] == null 
            || (lists[child] != null 
                && lists[index].val > lists[child].val)) {
                swap(lists, index, child);
                index = child;
                child = 2 * index + 1;
            } else {
            	break;
            }
        }
    }
    
    public void swap(ListNode[] lists, int idx1, int idx2) {
        ListNode temp = lists[idx1];
        lists[idx1] = lists[idx2]; 
        lists[idx2] = temp;
    }
    

    }


  • 0
    L

    Use PriorityQueue,it is a heap。


  • 0

    cool, thanks. I will try it.

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }
        ListNode head = null;
        ListNode tail = null;
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){
            public int compare(ListNode node1, ListNode node2) {
                return node1.val - node2.val;
            }
        });
        
        for(ListNode node : lists) {
            if(node != null) {
                heap.add(node);
            }
        }
        
        while(heap.peek() != null) {
            ListNode curr = heap.poll();
            if(curr.next != null) {
                heap.offer(curr.next);
            }
            
            if(head == null) {
                head = curr;
            }
            
            if(tail != null) {
                tail.next = curr;
            }
            tail = curr;
        }
        return head;
    }

Log in to reply
 

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