Leetcode 23 - Merge k Sorted Lists（K路归并）

题意

合并k个有序链表。

思路

k路归并。

算法1

维护一个大小为k的堆。

维护一个大小为k的小顶堆，开始的时候将这k个链表的头结点扔到堆里面去（如果为null，不扔进去，并且我们维护的堆的大小相应的减小）。每次，从堆顶弹出一个节点t，加入我们的结果链表中。如果t对应链表的后面的一个节点为空，do nothing；否则，将t后面的一个节点假如到堆里面。重复过程3,4直到堆为空。

时间复杂度： O(nklogk) 。

其中n为每条链表的节点数目（实际上每条链表的节点数目不一定相等，我们这里假设 nk 为节点的总数目），k为链表的条数。因为一共有nk个节点，并且节点会进堆一次，出堆一次，push和pop的时间复杂度是 O(logk) ，所以总的时间复杂度为 O(nklogk) 。

算法2

分治，两两归并。

我们利用之间的mergeTwoSortedList，将k个链表先将前面的k/2个链表归并成一个链表l1，后面的k/2个链表归并成另一个链表l2，然后再将l1和l2这两个有序链表合成新的有序链表。

时间复杂度： O(nklogk)

假设链表的长度相等都为n，有k个链表。那么我们总的时间为：

2⋅nk2+4⋅nk4+...+2m⋅nkm=∑i=1mnk

其中 m=log(k) ，则时间复杂度为 nklog(k) 。

代码

algorithm 1

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ //algorithm 1 struct cmp { bool operator()(ListNode *x, ListNode *y) { return y->val < x->val; } }; class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, cmp> q; int k = lists.size(), cnt = 0; for (int i = 0; i < k; i++) { if (lists[i]) q.push(lists[i]); } ListNode *head = new ListNode(0), *p = head; while (!q.empty()) { ListNode *t = q.top(); q.pop(); p->next = t; p = p->next; t = t->next; if (t) q.push(t); } return head->next; } };

algorithm 2

class Solution { public: ListNode* mergeTwoList(ListNode *l1, ListNode *l2) { ListNode *head = new ListNode(0), *p = head; while (l1 || l2) { ListNode *t; if (l1 && l2) t = l1->val < l2->val ? l1 : l2; else if (l1) t = l1; else t = l2; p->next = t; p = p->next; t == l1 ? l1 = l1->next : l2 = l2->next; } return head->next; } ListNode* merge(int l, int r, vector<ListNode*>& v) { if (l > r) return nullptr; if (l == r) return v[l]; if (r == l + 1) return mergeTwoList(v[l], v[r]); int m = l + (r - l >> 1); return mergeTwoList(merge(l, m, v), merge(m + 1, r, v)); } ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(0, lists.size() - 1, lists); } };