?

描述

合并 k?個升序的鏈表并將結果作為一個升序的鏈表返回其頭節點。

數據范圍：節點總數?0 \le n \le 50000≤n≤5000，每個節點的val滿足?|val| <= 1000∣val∣<=1000

要求：時間復雜度?O(nlogn)O(nlogn)

示例1

輸入：

[{1,2,3},{4,5,6,7}]

返回值：

{1,2,3,4,5,6,7}

示例2

輸入：

[{1,2},{1,4,5},{6}]

返回值：

{1,1,2,4,5,6}

解題報告：

區分于歸并排序。歸并排序是說，給定一個無序數組給排序成有序數組。

這個是說，給定K個有序鏈表，要求合并成一個有序鏈表

當然，本質的merge(h1, h2)函數沒變，都是把兩個有序序列給合并成一個有序序列。

這題還有一種做法，不過空間復雜度較高一些，時間復雜度是一樣的，就是用優先隊列來存K個鏈表的頭結點，然后排序這樣子。

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *mergeKLists(vector<ListNode *> &lists) {return mergeList(lists, 0, lists.size()-1);}ListNode* mergeList(vector<ListNode *> lists, int l, int r) {if(l == r) {return lists[l];}if(l > r) {return nullptr;}int mid = (l+r)/2;return mer(mergeList(lists, l, mid), mergeList(lists, mid+1, r));}ListNode* mer(ListNode* h1, ListNode* h2) {ListNode* head = new ListNode(-1);ListNode* p = head;while(h1 && h2) {if(h1->val < h2->val) {p->next = h1;h1 = h1->next;p = p->next;} else {p->next = h2;h2 = h2->next;p = p->next;}}if(h1) p->next = h1;else p->next = h2;return head->next;} };

總結

以上是生活随笔為你收集整理的【NC51 合并k个已排序的链表】K路归并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。