LeetCode Merge k Sorted Lists

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

题意：将k个已经排好序的链表合并成一个

思路：用到优先队列比较简单。

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */struct cmp{bool operator() (ListNode *a, ListNode *b) {return a->val > b->val;}};class Solution {public:ListNode *mergeKLists(vector<ListNode *> &lists) {priority_queue<ListNode *, vector<ListNode *>, cmp> queue;for (int i = 0; i < lists.size(); i++) {if (lists[i] != NULL)queue.push(lists[i]);}ListNode *head = NULL, *pre = NULL, *tmp;while (!queue.empty()) {tmp = queue.top();queue.pop();if (pre == NULL) head = tmp;else pre->next = tmp;pre = tmp;if (tmp->next != NULL)queue.push(tmp->next);}return head;}};

，你可以选择这样的“三心二意”：信心恒心决心;创意乐意。