A java solution based on Priority Queue


  • 176
    R

    If someone understand how priority queue works, then it would be trivial to walk through the codes.

    My question: is that possible to solve this question under the same time complexity without implementing the priority queue?

    public class Solution {
        public ListNode mergeKLists(List<ListNode> lists) {
            if (lists==null||lists.size()==0) return null;
            
            PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
                @Override
                public int compare(ListNode o1,ListNode o2){
                    if (o1.val<o2.val)
                        return -1;
                    else if (o1.val==o2.val)
                        return 0;
                    else 
                        return 1;
                }
            });
            
            ListNode dummy = new ListNode(0);
            ListNode tail=dummy;
            
            for (ListNode node:lists)
                if (node!=null)
                    queue.add(node);
                
            while (!queue.isEmpty()){
                tail.next=queue.poll();
                tail=tail.next;
                
                if (tail.next!=null)
                    queue.add(tail.next);
            }
            return dummy.next;
        }
    }

  • 2
    I

    Could you please explain what the current complexity is?


  • 3
    R

    Suppose the total number of nodes is n The total time complexity if (n * log k) .For a priority queue, insertion takes logK time


  • 203
    W

    I think my code's complexity is also O(nlogk) and not using heap or priority queue, n means the total elements and k means the size of list.

    The mergeTwoLists functiony in my code comes from the problem Merge Two Sorted Lists whose complexity obviously is O(n), n is the sum of length of l1 and l2.

    To put it simpler, assume the k is 2^x, So the progress of combination is like a full binary tree, from bottom to top. So on every level of tree, the combination complexity is n, beacause every level have all n numbers without repetition. The level of tree is x, ie logk. So the complexity is O(nlogk).

    for example, 8 ListNode, and the length of every ListNode is x1, x2,
    x3, x4, x5, x6, x7, x8, total is n.

    on level 3: x1+x2, x3+x4, x5+x6, x7+x8 sum: n

    on level 2: x1+x2+x3+x4, x5+x6+x7+x8 sum: n

    on level 1: x1+x2+x3+x4+x5+x6+x7+x8 sum: n

    total 3n, nlog8

    public class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    
            ListNode head=null;
            ListNode former=null;
            while (l1!=null&&l2!=null) {
                if (l1.val>l2.val) {
                    if (former==null) former=l2; else former.next=l2;
                    if (head==null) head=former; else former=former.next;
                    l2=l2.next;
                } else {
                    if (former==null) former=l1; else former.next=l1;
                    if (head==null) head=former; else former=former.next;
                    l1=l1.next;
                }
            }
            if (l2!=null) l1=l2;
            former.next=l1;
            return head;
            
        }
        
        public ListNode mergeKLists(List<ListNode> lists) {
            if (lists.size()==0) return null;
            if (lists.size()==1) return lists.get(0);
            if (lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
            return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)), 
                mergeKLists(lists.subList(lists.size()/2, lists.size())));
        }
    }
    

  • 2
    L

    This code can do one more improvement. Once there is only 1 element in the heap, you can use code : tail.next = queue.poll(); to finish it. Because on that condition, all original lists except one list are merged to the result list. So we can attach the remaining list to the tail of result list and don't need to go through all the remaining nodes.


  • 1
    D

    you could optimize using an iterator for list in you for clause


  • 0
    R

    Point well made.


  • 5
    Z

    I have the same solution.
    You can reduce the comparer code using Integer.compare():

       public class Solution {
            public ListNode mergeKLists(List<ListNode> lists) {
                if(lists.size() == 0)
                    return null;
                PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(11, new ListNodeComparer());
                for(ListNode node: lists) {
                    if(node != null)
                        queue.add(node);
                }
                if(queue.isEmpty())
                    return null;
    
                ListNode result = queue.poll();
                if(result.next != null)
                    queue.add(result.next);
    
                ListNode cur = result;
    
                while(!queue.isEmpty()) {
                    ListNode node = queue.poll();
                    if(node.next != null) {
                        queue.add(node.next);
                        node.next = null;
                    }
                    cur.next = node;
                    cur = cur.next;
                }
    
                return result;
            }
    
            private class ListNodeComparer implements Comparator<ListNode> {
                @Override
                public int compare(ListNode o1, ListNode o2) {
                    return Integer.compare(o1.val, o2.val);
                }
            }
        }

  • 3
    H

    use heap

        public class Solution {
    class Heap {
    	public List<ListNode> heap;
    
    	private int getLimit() {
    		return heap.size() - 1;
    	}
    
    	Heap(List<ListNode> lists) {
    		heap = new ArrayList<ListNode>();
    		heap.add(new ListNode(0));
    		int i = 0;
    		while (i < lists.size()) {
    			if (lists.get(i) != null)
    				heap.add(lists.get(i));
    			++i;
    		}
    	}
    
    	public void heapAdjust(int n, int m) {
    		ListNode value = new ListNode(0);
    		copy(heap.get(n), value);
    		for (int i = 2 * n; i <= m; i *= 2) {
    			if (i < m && heap.get(i).val > heap.get(i + 1).val)
    				i++;
    			if (heap.get(i).val >= value.val)
    				break;
    			copy(heap.get(i), heap.get(n));
    			n = i;
    		}
    		copy(value, heap.get(n));
    	}
    
    	private void copy(ListNode s, ListNode t) {
    		if (s == null)
    			s = new ListNode(t.val);
    		t.next = s.next;
    		t.val = s.val;
    	}
    
    	public void creatMinHeap() {
    		for (int i = getLimit() / 2; i > 0; --i)
    			heapAdjust(i, getLimit());
    	}
    
    	public ListNode getHeap() {
    		if (heap.size() == 1)
    			return null;
    		if (heap.get(1) == null) {
    			return null;
    		}
    		ListNode result = new ListNode(0);
    		copy(heap.get(1), result);
    		if (heap.get(1).next != null)
    			copy(heap.get(1).next, heap.get(1));
    		else {
    			copy(heap.get(heap.size() - 1), heap.get(1));
    			heap.remove(heap.size() - 1);
    		}
    		if (heap.size() != 1)
    			heapAdjust(1, getLimit());
    		return result;
    	}
    
    	public int getlen() {
    		return heap.size() - 1;
    	}
    }
    
    public ListNode mergeKLists(List<ListNode> lists) {
    	Heap h = new Heap(lists);
    	h.creatMinHeap();
    	ListNode result = null;
    	if (h.getlen() != 0)
    		result = h.getHeap();
    	else
    		return result;
    	ListNode temp = result;
    	while (h.getlen() != 0 && temp != null) {
    		temp.next = h.getHeap();
    		temp = temp.next;
    	}
    	return result;
    
    }
    }

  • 0
    A

    I guess this is why it's tagged as divide and conquer


  • 0
    S

    Cool! This question used to my one of my mid-term question in Algorithm class. And my teacher didn't mention this simple but powerful idea. I vote up!


  • 0
    J

    Is Java priority queue the same thing as heap in C++?


  • 1
    R

    my solution without using heap,priority queue

    public class Solution {
        public ListNode mergeKLists(List<ListNode> lists) {
            if (lists.size() == 0 ) {
                return null;
            } else if (lists.size() == 1 ) {
                return lists.get(0);
            } else {
                int mid = lists.size() / 2;
                ListNode a = mergeKLists(lists.subList(0,mid));
                ListNode b = mergeKLists(lists.subList(mid,lists.size()));
                if ( a == null || b == null ) {
                    return a == null ? b : a;
                }
                ListNode h = null;
                if ( a.val < b.val) {
                    h = a;
                    a = a.next;
                } else {
                    h = b;
                    b = b.next;
                }
                ListNode l = h;
                while ( a != null && b != null ) {
                    if ( a.val < b.val ) {
                        l.next = a;
                        a = a.next;
                    } else {
                        l.next = b;
                        b = b.next;
                    }
                    l = l.next;
                }
                if ( a != null ) {
                    l.next = a;
                } else if ( b != null ) {
                    l.next = b;
                }
                return h;
            }
        }
    }

  • 0
    E

    Very nice explanation.


  • 0
    K

    o1.val - o2.val


  • 0
    K

    Very nice solution! If I am not wrong, space cost of O(log k) is even better than O(k) of the heap solution!


  • 0
    M

    Here's an iterative version of Divide and Conquer style merging, same time complexity without using priority queue.

    Each iteration shrinks the list by a factor of 2, but be careful for boundary conditions.

    public class Solution {
        public ListNode mergeKLists(List<ListNode> lists) {
            if (lists == null || lists.isEmpty()) return null;
            int n = lists.size() - 1;
            
            while (n > 0) {
                for (int i = 0; i < (n + 1) / 2; i++) {
                    lists.set(i, merge(lists.get(i), lists.get(n - i)));
                }
                n /= 2;
            }
            
            return lists.get(0);
        }
        
        private ListNode merge(ListNode node1, ListNode node2) {
            ListNode virtual = new ListNode(0);
            ListNode node = virtual;
            
            while (node1 != null || node2 != null) {
                if (node2 == null || (node1 != null && node1.val < node2.val)) {
                    node.next = node1;
                    node1 = node1.next;
                } else {
                    node.next = node2;
                    node2 = node2.next;
                }
                node = node.next;
            }
            
            return virtual.next;
        }
    }

  • 0
    Y

    You actually build a heap.


  • 0
    R

    Great solution!


  • 0
    L
    This post is deleted!

Log in to reply
 

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