23. Merge k Sorted Lists

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

---

归并k个已排序的链表。 之前是归并2个已排序的链表，现在变成多个了。其实就是多路归并，思路之前都知道，不同思路的区别就在于怎样找到所有链表当前位置的最小值，可以直接线性查找，也可以用败者树、胜者树或者堆。我一开始用线性查找，不出意外的TLE了，后来改用建堆的方法，顺利通过。 写代码越来越懒了，直接上STL，需要注意的是STL中的make_heap默认建的是大顶堆，我们需要传自己的比较函数进去以便构建小顶堆。

typedef struct Node {
    ListNode* ln;
    int idx;
    bool operator<(const Node& p) const { return this->ln->val < p.ln->val; }
    bool operator>(const Node& p) const { return this->ln->val > p.ln->val; }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        ListNode *ans = new ListNode(0), *head = ans;
        vector<Node> vn;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL) {
                Node nd;
                nd.ln = lists[i];
                nd.idx = i;
                vn.push_back(nd);
                lists[i] = lists[i]->next;
            }
        }
        if (vn.size() == 0)
            return NULL;
        make_heap(vn.begin(), vn.end(), greater<Node>());
        while (true) {
            Node tmp = vn.front();
            ans->next = tmp.ln;
            ans = ans->next;
            pop_heap(vn.begin(), vn.end(), greater<Node>());
            vn.pop_back();
            if (lists[tmp.idx] != NULL) {
                tmp.ln = lists[tmp.idx];
                vn.push_back(tmp);
                push_heap(vn.begin(), vn.end(), greater<Node>());
                lists[tmp.idx] = lists[tmp.idx]->next;
            }
            if (vn.empty())
                break;
        }
        return head->next;
    }
};

本代码提交AC，用时420MS。

二刷。更简单的是直接使用STL的优先队列，代码如下：

struct LNNode {
	ListNode* ln;
	LNNode() :ln(NULL) {};
	bool operator<(const LNNode& ln_) const{ // 注意两个const都不能少
		return ln->val > ln_.ln->val;
	}
};
class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<LNNode> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				LNNode cur;
				cur.ln = lists[i];
				pq.push(cur);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			LNNode cur = pq.top();
			pq.pop();
			root->next = cur.ln;
			root = root->next;
			if (cur.ln->next) {
				LNNode nxt;
				nxt.ln = cur.ln->next;
				pq.push(nxt);
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时32MS。

或者不用定义新的类，直接用原来的ListNode*，但新增一个比较函数，代码如下：

struct cmp {
	bool operator()(ListNode* l1, ListNode* l2) {
		return l1->val > l2->val;
	}
};

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				pq.push(lists[i]);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			ListNode* cur = pq.top();
			pq.pop();
			root->next = cur;
			root = root->next;
			if (cur->next) {
				pq.push(cur->next);
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时32MS。