Merge K Sorted List

题目

[23] Merge k Sorted Lists  

https://leetcode.com/problems/merge-k-sorted-lists/description/

* algorithms
* Hard (35.68%)
* Total Accepted:    444.4K
* Total Submissions: 1.2M
* Testcase Example:  '[[1,4,5],[1,3,4],[2,6]]'

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

Example:


Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

思路

我们已经有了merge-2-sorted-lists的解法，这道题只需迭代调用。

但是有个问题很关键，就是我们到底要合并多少次呢？ 如果是每次把新的list合并到结果中，据说会超时。

这个时候的时间复杂度是2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^2)

不过反正我用递归的话并没有超时。

def merge_k_lists(lists)
  if lists.count == 0
    return nil
  end
  if lists.count == 1
    return lists[0]
  end
  if lists.count == 2
    return merge_two_lists(lists[0], lists[1])
  else
    list = merge_k_lists(lists[1..-1])
    return merge_two_lists(lists[0], list)
  end
end

def merge_two_lists(l1, l2)
  i = l1
  j = l2
  if l1 == nil
      return l2 ? l2 : nil
  elsif l2 == nil
      return l1 ? l1 : nil
  end
  if l1.val > l2.val 
    head = l2
    j = j.next
  else
    head = l1
    i = i.next
  end
  current = head
  while i && j
    if i.val < j.val
      current.next = i
      i = i.next
    else
      current.next = j
      j = j.next
    end
    current = current.next
  end
  while i
    current.next = i
    i = i.next
    current = current.next
  end
  while j
    current.next = j
    j = j.next
    current = current.next
  end
  return head
end

分治法解法

同样利用已经写好的merge-2-sorted-lists, 只不过这次通过两两合并来减少合并次数。
时间复杂度为时间复杂度为O(nk log(k))

最小堆排序解法

首先复习一下堆的概念。堆可以分为最小堆和最大堆。就最小堆来说，就是对于一棵二叉树，root节点总是保持最小。
任何父节点总是小于叶子节点。

最小堆主要有push和pop操作。

push： 将新元素插入到最后的叶子节点，并于父节点比较，如果小于父节点，则交换。如此循环直到遇到比自己小的父节点或者最后到root节点。

pop： 获取最小元素，由上往下比较左右两子节点，将子节点中较大的节点作为新的父节点，不断重复，直到叶子节点。

对于解决 merge-k-sorted-lists问题，我们可以先将k个list中的第一个元素组成一个堆。
每次取堆顶元素root，放入result中，然后把root.next插入到堆中。这样可以保证我们每次从堆顶获取的元素都是最小的。

class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};

反思

堆是一个陌生的数据结构。需要特别留意。