[LeetCode]Merge k Sorted Lists

为了方便计算时间复杂度，先假设有n个list，每个list的长度为m。首先我们可以想到的一个方法是，每个list不断地和第一个list merge，直到我们只剩第一个list为止。这样的话，要进行n - 1次merge，第一个list里每个元素会被扫n - 1次，第二个list里每个元素会被扫n - 2次，以此类推。所以总的时间复杂度是O(n * n * m)。然后我们应该能很快想到一个提高的方法就是两两merge，这样merge的过程就像一个二叉树，在每层每个元素会被扫一次，有log n层，所以时间复杂度是O(n * m * log n)。代码如下：

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode mergeKLists(List<ListNode> lists) {
	if (lists == null || lists.size() == 0)
	return null;
	while (lists.size() > 1) {
	int len = lists.size();
	for (int i = 0; i < len / 2; i++) {
	ListNode node1 = lists.remove(0);
	ListNode node2 = lists.remove(0);
	ListNode newNode = merge(node1, node2);
	lists.add(newNode);
	}
	}
	return lists.get(0);
	}
	private ListNode merge(ListNode node1, ListNode node2) {
	if (node1 == null)
	return node2;
	if (node2 == null)
	return node1;
	ListNode head = node1.val < node2.val? node1: node2, curr = head;
	if (node1 == head)
	node1 = node1.next;
	if (node2 == head)
	node2 = node2.next;
	while (node1 != null && node2 != null) {
	if (node1.val <= node2.val) {
	curr.next = node1;
	node1 = node1.next;
	} else {
	curr.next = node2;
	node2 = node2.next;
	}
	curr = curr.next;
	}
	if (node1 != null)
	curr.next = node1;
	if (node2 != null)
	curr.next = node2;
	return head;
	}
	}

view raw merge k sorted list v-1.java hosted with ❤ by GitHub

另外一个方法就是，维护一个heap，每次从heap中删掉最小的值，然后把删掉元素的next元素加入，每个元素要进一次出一次heap，时间复杂度也是O(n * m * log n)，代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	auto comp = [](const ListNode* n1, const ListNode* n2)
	{
	return n1->val > n2->val;
	};
	priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
	for(const auto node : lists)if(node)pq.push(node);
	ListNode* head = nullptr, *tail = nullptr;
	while(pq.size())
	{
	auto curr = pq.top();
	pq.pop();
	if(!head)
	{
	head = curr;
	tail = curr;
	}
	else
	{
	tail->next = curr;
	tail = tail->next;
	}
	if(curr->next)
	pq.push(curr->next);
	}
	return head;
	}
	};

view raw Merge k Sorted Lists.cpp hosted with ❤ by GitHub