LeetCode 23 - Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

• Priority Heap

Time complexity : $O(N\log k)$ where $\text{k}$ is the number of linked lists.

• The comparison cost will be reduced to $O(\log k)$ for every pop and insertion to priority queue. But finding the node with the smallest value just costs $O(1)$ time.
• There are $N$ nodes in the final linked list.

https://leetcode.com/articles/merge-k-sorted-list/

public ListNode mergeKLists(ArrayList<ListNode> lists) {
  if (lists == null || lists.isEmpty())   // Empty lists
          return null;
  int k = lists.size();
  // Use a heap (priority queue) to process
  PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(k, new Comparator<ListNode>() {
      @Override
      public int compare(ListNode n1, ListNode n2) {
          return n1.val-n2.val;
      }
  });
  // Put the first (smallest) node into the heap
  for (ListNode node : lists) {
      if (node != null)
          heap.offer(node);
  }
  ListNode head = new ListNode(0), tail = head;   // Use a header to avoid boundary check
  // Put the smallest in the heap to the resulting list,
  // and add its next node (if any) to the heap
  while (!heap.isEmpty()) {
      ListNode temp = heap.poll();
      tail.next = temp;
      tail = tail.next;
      if (temp.next != null)
          heap.offer(temp.next);
  }
  return head.next;
}

https://leetcode.com/problems/merge-k-sorted-lists/discuss/10528/A-java-solution-based-on-Priority-Queue

    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;
    }

http://yuanhsh.iteye.com/blog/2229665

1. public static class Node {  
2.     int index = 0;  
3.     List<Integer> list;  
4.     public Node(List<Integer> list) {  
5.         this.list = list;  
6.     }  
7.       
8.     public int peek() {  
9.         return list.get(index);  
10.     }  
11.   
12.     public int next() {  
13.         return list.get(index++);  
14.     }  
15.       
16.     public boolean hasNext() {  
17.         return index < list.size();  
18.     }  
19. }  
20. List<Integer> sortData(List<List<Integer>> numArray) {  
21.     List<Integer> result = new ArrayList<>();  
22.     Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>(){  
23.         public int compare(Node n1, Node n2) {  
24.             return n1.peek() - n2.peek();  
25.         }  
26.     });  
27.     for(List<Integer> list:numArray) {  
28.         if(list != null && list.size() > 0) {  
29.             queue.offer(new Node(list));  
30.         }  
31.     }  
32.     while(!queue.isEmpty()) {  
33.         Node node = queue.poll();  
34.         result.add(node.next());  
35.         if(node.hasNext()) {  
36.             queue.offer(node);   
37.         }  
38.     }  
39.     return result;  
40. }  

X. Approach 4: Merge lists one by one

• Time complexity : $O(kN)$ where $\text{k}$ is the number of linked lists.
  • We can merge two sorted linked list in $O(n)$ time where $n$ is the total number of nodes in two lists.
  • Sum up the merge process and we can get: $O(\sum_{i=1}^{k-1} (i*(\frac{N}{k}) + \frac{N}{k})) = O(kN)$.

Approach 5: Merge with Divide And Conquer

Time complexity : $O(N\log k)$ where $\text{k}$ is the number of linked lists.

• We can merge two sorted linked list in $O(n)$ time where $n$ is the total number of nodes in two lists.
• Sum up the merge process and we can get: $O\big(\sum_{i=1}^{log_{2}{k}}N \big)= O(N\log k)$​N)=O(Nlogk)

https://leetcode.com/problems/merge-k-sorted-lists/discuss/152022/Divide-and-Conquer-Heap-with-Explanations

Divide and Conquer
The problem is easier to solve if we think in a Divide and Conquer way.

1. Divide: Break the given problem into subproblems of same type.
2. Conquer: Recursively solve these subproblems
3. Combine: Appropriately combine the answers

It is always implemented by recursion.

• base case:
  If there is only one list in lists[], we simply return it for it is in order naturally.
• to reduce the problem to the base case:
  we keep splitting lists[] into two parts in the middle, and we will obtain base cases in the last.
• to merge the subproblems:
  as what we do in MergeSort using two pointers

    public ListNode mergeKLists(ListNode[] lists) {
        // Corner cases.
        if (lists == null || lists.length == 0)
            return null;
        
        return mergeKLists(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeKLists(ListNode[] lists, int start, int end) {
        // Base cases.
        if (end < start) {
            return null;
        }
        if (end - start == 0) {
            return lists[start];
        }
        if (end - start == 1) {
            return mergeTwoLists(lists[start], lists[end]);
        }
        
        // Divide lists into 2 sublists and sort them as a whole recursively.
        int mid = start + ((end - start) >> 1);
        ListNode lower = mergeKLists(lists, start, mid);
        ListNode upper = mergeKLists(lists, mid + 1, end);
        
        return mergeTwoLists(lower, upper);
    }
    
    private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0), ptr = dummyHead;
        
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                ptr.next = head1;
                head1 = head1.next;
            } else {
                ptr.next = head2;
                head2 = head2.next;
            }
            ptr = ptr.next;
        }
        if (head1 != null) {
            ptr.next = head1;
        } else if (head2 != null) {
            ptr.next = head2;
        }
        return dummyHead.next;
    }

https://leetcode.com/problems/merge-k-sorted-lists/discuss/11010/A-solution-use-divide-and-conquer-algorithm-in-java
- Using subList

public ListNode mergeKLists(List<ListNode> lists) {
        int length = lists.size() ;

        if(length == 0)
            return null ;
        if(length == 1){
            return lists.get(0) ;
        }

        int mid = (length - 1)/2 ;
        ListNode l1 = mergeKLists(lists.subList(0,mid + 1)) ;
        ListNode l2 = mergeKLists(lists.subList(mid + 1,length)) ;

        return mergeTowLists(l1,l2) ;

    }

    public ListNode mergeTowLists(ListNode l1 , ListNode l2){
        ListNode result = new ListNode(0) ;
        ListNode list = result ;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                list.next = l1 ;
                l1 = l1.next ;
            }else{
                list.next = l2 ;
                l2 = l2.next ;
            }
            list = list.next ;
        }

        while(l1 != null){
            list.next = l1 ;
            l1 = l1.next ;
            list = list.next ;
        }

        while(l2 != null){
            list.next = l2 ;
            l2 = l2.next ;
            list = list.next ;
        }

        return result.next ;
    }

http://www.cnblogs.com/TenosDoIt/p/3673188.html

最傻的做法就是先1、2合并，12结果和3合并，123结果和4合并，…,123..k-1结果和k合并，我们计算一下复杂度。

1、2合并，遍历2n个节点

12结果和3合并，遍历3n个节点

123结果和4合并，遍历4n个节点

…

123..k-1结果和k合并，遍历kn个节点

总共遍历的节点数目为n(2+3+…+k) = n*(k^2+k-2)/2, 因此时间复杂度是O(n*(k^2+k-2)/2) = O(nk^2)，代码如下：

ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.size() == 0)return NULL;
        ListNode*res = lists[0];
        for(int i = 1; i < lists.size(); i++)
                res = merge2list(res, lists[i]);
        return res;
}
ListNode *merge2list(ListNode *head1, ListNode*head2)
{
        ListNode node(0), *res = &node;
        while(head1 && head2)
        {
                if(head1->val <= head2->val)
                {
                        res->next = head1;
                        head1 = head1->next;
                }
                else
                {
                        res->next = head2;
                        head2 = head2->next;
                }
                res = res->next;
        }
     if(head1)
                res->next = head1;
        else if(head2)
                res->next = head2;
        return node.next;
}

算法2：利用分治的思想把合并k个链表分成两个合并k/2个链表的任务，一直划分，知道任务中只剩一个链表或者两个链表。可以很简单的用递归来实现。因此算法复杂度为T(k) = 2T(k/2) + O(nk),很简单可以推导得到算法复杂度为O（nklogk）

递归的代码就不贴了。下面是非递归的代码非递归的思想是（以四个链表为例）

1、3合并，合并结果放到1的位置

2、4合并，合并结果放到2的位置

再把1、2合并（相当于原来的13 和 24合并）

ListNode *mergeKLists(vector<ListNode *> &lists) {
         int n = lists.size();
         if(n == 0)return NULL;
         while(n >1)
         {
                 int k = (n+1)/2;
                 for(int i = 0; i < n/2; i++)
                         lists[i] = merge2list(lists[i], lists[i + k]);
                 n = k;
         }
         return lists[0];
 }
 ListNode *merge2list(ListNode *head1, ListNode*head2)
 {
         ListNode node(0), *res = &node;
         while(head1 && head2)
         {
                 if(head1->val <= head2->val)
                 {
                         res->next = head1;
                         head1 = head1->next;
                 }
                 else
                 {
                         res->next = head2;
                         head2 = head2->next;
                 }
                 res = res->next;
         }
         if(head1)
                 res->next = head1;
         else if(head2)
                 res->next = head2;
         return node.next;
 }

http://www.lifeincode.net/programming/leetcode-merge-k-sorted-lists-java/
Recursive version
It’s similar to merge sort. For example, assuming we have 4 lists: 1, 2, 3, 4. We can merge 1 and 2 to be a new list 5. And 3 and 4 can be merged to be a new list 6. Finally we merge 5 and 6 to get the result. So in this algorithm, we divide the lists by 2 until its size reaches 1. And then merge them from bottom to top.

    public ListNode mergeKLists(List<ListNode> lists) {

        if (lists.size() == 0)

            return null;

        return mergeKLists(lists, 0, lists.size() - 1);

    }

    

    public ListNode mergeKLists(List<ListNode> lists, int left, int right) {

        if (left < right) {

            int mid = (left + right) / 2;

            return merge(mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right));

        }

        return lists.get(left);

    }

    

    public ListNode merge(ListNode m, ListNode n) {

        ListNode head = new ListNode(0);

        ListNode p = head;

        while (m != null && n != null) {

            if (m.val < n.val) {

                p.next = m;

                p = p.next;

                m = m.next;

            } else {

                p.next = n;

                p = p.next;

                n = n.next;

            }

        }

        if (m != null)

            p.next = m;

        else

            p.next = n;

        return head.next;

    }

Recursive version: We have T(n) = 2T(n/2) + kn. So the complexity is O(kn logn). The depth of the recursive function is O(log n). 

Priority queue version: Every time we add a new element to the queue, it costs O(log n). And we have kn elements. So the complexity is O(kn logn) + O(kn) = O(kn logn). And the space complexity is only O(n).

https://github.com/yadongwen/leetcode/blob/master/Merge%20k%20Sorted%20Lists.java

http://buttercola.blogspot.com/2015/11/linkedin-merge-k-sorted-iterators.html
interface是这个 Iterable<Integer> mergeKSortedIterators(Iterators[] iters)
也就是给每个array的iterator,然后merge. => only have next method

Solution:
The problem looks straight-forward: just to a minHeap and continuously poll and add elements into the heap. 

The only pitfall for this problem is the input is Iterators. When we compare values in the heap, if we use next(), we might lose the next() value. Thus we need to defined a customized class to store the value. 

public static Iterable<Integer> mergeKSortedIterators(List<Iterator<Integer>> iterators) {
        List<Integer> result = new ArrayList<>();
        if (iterators == null || iterators.size() == 0) {
                return result;
        }
        PriorityQueue<MyIterator> pq = new PriorityQueue<>(iterators.size());
        for (Iterator<Integer> iterator : iterators) {
                if (iterator.hasNext()) {
                        pq.add(new MyIterator(iterator.next(), iterator));
                }
        }
        while (!pq.isEmpty()) {
                MyIterator curr = pq.poll();
                result.add(curr.val);
                if (curr.hasNext()) {
                        pq.add(curr);
                }
        }
        return result;
}
private static class MyIterator implements Comparable<MyIterator> {
        private Integer val;
        private Iterator<Integer> iterator;
        public MyIterator(Integer val, Iterator<Integer> iterator) {
                this.val = val;
                this.iterator = iterator;
        }
        public boolean hasNext() {
                if (iterator.hasNext()) {
                        val = iterator.next();
                        return true;
                }
                return false;
        }
        public int compareTo(MyIterator that) {
                return this.val - that.val;
        }
}

X. Brute Force

public ListNode mergeKLists(ListNode[] lists) {

   if (null == lists || lists.length == 0) {

       return null;

   }

   ListNode res = lists[0];

   for (int i = 1; i < lists.length; i++) {

       res = mergeTwoLists(res, lists[i]);

   }

   return res;

}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {

   ListNode dummy = new ListNode(-1);

   ListNode head = dummy;

   while (l1 != null && l2 != null) {

       if (l1.val <= l2.val) {

           head.next = l1;

           l1 = l1.next;

       } else {

           head.next = l2;

           l2 = l2.next;

       }

       head = head.next;

   }

   if (l1 != null) {

       head.next = l1;

   } else {

       head.next = l2;

   }

   return dummy.next;

}

http://lifexplorer.me/leetcode-merge-k-sorted-lists/

public ListNode mergeKLists(List<ListNode> lists) {

    int n = lists.size();

    if(n == 0) {

        return null;

    }

    while(n > 1) {

        // Notice the boundary, key part

        // i + k = n/2 - 1 + (n+1)/2 = n - 1

        int k = (n + 1) / 2;

        for(int i = 0; i < n/2; i++) {

            lists.set(i, mergeTwoLists(lists.get(i), lists.get(i + k)) );

        }

        n = k;

    }

    return lists.get(0);

}

https://github.com/mission-peace/interview/blob/master/src/com/interview/array/ChunkMerge.java

1. merge之后实现⼀一个iterator class， 实现hasNext()和next()
2. 简化版为21
3. 另⼀一版本为List<Integer>（参考281）
2. 23 list maybe null
(code)
3. Iterator (code)
4. List<Integer> iterator ⾃自带的iter不不 能⽤用因为pq要⽐比较
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/K%20Sorted%20Lists%20Iterator/KSortedListNode.java

    public class KListIterator {

        PriorityQueue<ListNode> pq;

        public KListIterator(ListNode[] lists) {
            pq = new PriorityQueue<>(new Comparator<ListNode>() {
                public int compare(ListNode a, ListNode b) {
                    return a.val - b.val;
                }
            });
            for (ListNode list : lists)
                if (list != null)
                    pq.add(list);
        }

        public boolean hasNext() {
            return !pq.isEmpty();
        }

        public int next() {
            ListNode cur = pq.poll();
            if (cur.next != null)
                pq.add(cur.next);
            return cur.val;
        }

    }

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/023_Merge_k_Sorted_Lists.java

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        });
        for (ListNode list : lists) 
            if (list != null) pq.add(list);
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!pq.isEmpty()) {
            tail.next = pq.poll();
            tail = tail.next;
            if (tail.next != null)
                pq.add(tail.next);
        }
        return head.next;
    }