题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
可以将各个链表的值获取到一个整型向量中,排序后再创建一个链表进行赋值。
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { private: int order = 0; public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ ListNode* mergeKLists(vector<ListNode*>& lists) { // write code here auto result = new ListNode(0); if(lists.size() == 0) { return nullptr; } vector<int> num; int length = 0; for(int i = 0; i < lists.size(); i++) { collect(lists[i], num); length = order; } if(num.size() == 0) { return nullptr; } sort(num.begin(), num.end()); order = 0; creatList(result, length, order, num); return result; } void collect(ListNode* head, vector<int>& num) { if(head == nullptr) { return; } num.push_back(head->val); order++; if(head->next == nullptr) { return; } collect(head->next, num); } void creatList(ListNode* head, int length, int order, vector<int>& num) { head->val = num.at(order); order++; if(order >= length) { return; } auto next = new ListNode(0); head->next = next; creatList(head->next, length, order, num); } };
较难(算法题解) 文章被收录于专栏
较难难度题目