這道題我是用最淳樸最簡單的思路去做的，用一個while循環持續地將當前遍歷到的最小值加入到合并鏈表中，while循環中使用一個for循環遍歷整個指針數組，將其中的最小值和對應下標記錄下來，并將其值加入到合并鏈表中，同時對應的那條鏈表的指針后移一位。這里我們需要用到一個額外的輔助變量flag，在每一次執行for循環之前需要初始化為false，默認為所有鏈表都已經遍歷到末尾，在for循環中，如果遇到了還沒遍歷到末尾的鏈表，則flag會被更新為true，該標志位的作用就是用來標記所有鏈表是否遍歷結束，如果遍歷結束就直接跳出外層的while循環。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* result = new ListNode();ListNode* temp = result;bool flag = lists.size() == 0 ? false : true;while(flag){int min_value = INT_MAX;int min_index = INT_MAX;flag = false;for(int i = 0; i < lists.size(); ++i){if(!lists[i]){ //若當前遍歷到的鏈表已經遍歷到末尾，則直接跳過當前鏈表flag = false || flag;continue; } flag = true; //尚有鏈表沒有遍歷結束if(lists[i] -> val < min_value){min_value = lists[i] -> val; //更新當前節點的最小值min_index = i; //更新最小值的下標}}if(flag){temp -> next = new ListNode(min_value);cout << min_value << endl;temp = temp -> next;lists[min_index] = lists[min_index] -> next;}}return result -> next;}
};
但是這么做的耗時有點太長了，AC之后去看了下靈神的題解，感覺他的第一種思路特別通俗易懂，主要是借用了數據結構本身的特性，利用優先隊列進行自動排序，而無需手動排序，因此我們只需要不斷地將節點加入到優先隊列中即可，這道題需要我們自定義一個排序規則，以對鏈表節點進行排序，當我們把優先隊列的隊頭元素（隊列內的最小值）取出后，我們需要判斷隊頭元素的下一個節點是否為空，若不為空才將下一個節點加入到優先隊列中。當所有鏈表的所有節點都被加入到優先隊列中后，我們直接退出循環。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* result = new ListNode();ListNode* temp = result;// 使用Lambda表達式定義比較規則auto compare = [] (const ListNode* a, const ListNode* b) {return a -> val > b -> val; //較小的優先級較高};priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> q; //優先隊列，存儲值較小的排前面for(auto head : lists){if(head) q.push(head); //將所有的非空鏈表頭節點入隊}while(!q.empty()){temp -> next = new ListNode(q.top() -> val);cout << q.top() -> val << endl;if(q.top() -> next) //下個節點不為空才入隊q.push(q.top() -> next);q.pop();temp = temp -> next;}return result -> next;}
};
)
