[LeetCode] 23. Merge k Sorted Lists

轉自LeetCode

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

<Solution>

這題是 Merge Two Sorted List 的延伸

現在有 k 個 list，最直接想法就是先 merge 兩個，然後再和之後每一個 merge

meage list_1 和 list_2，拿到 list_a
meage list_a 和 list_3，拿到 list_b
meage list_b 和 list_4，拿到 list_c

list_c 就是答案

但這樣不夠有效率

這題是要 merge 好 k 個 sorted list，其實就是在做 merge sort 一樣

要用 divide and conquer 的方式來處理

有 list_1，list_2，list_3，list_4

list_1 和 list_2 merge 得到 list_a，list_3 和 list_4 merge 得到 list_b

最後再 merge list_a 和 list_b 就可以得到答案

code 如下

解法 2 是運用到 min heap 的概念

可以使用 std::priority_queue，預設是 max heap

但只要改變用來比較的函數，就可以變成 min heap

使用 min heap 的想法如下

• 先把每個 list 的最小元素丟到 min heap

• 只要 min heap 不為空，持續以下動作

1. 拿出第一個元素，串到答案的 link list。因為 min heap 的特性，每次拿到的一定是當前最小的元素


2. 檢查當前的元素是否是最後一個元素，不是的話，再丟進去 min heap

code 如下

c++


Kotlin