Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
算法一,自底至頂遞歸。
時間復雜度為O(nlogk)。
空間復雜度為O(k)。
此算法在leetcode上實際執行時間為 144ms (130 test cases)。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeKLists(vector&lists) { if (lists.empty()) return 0; if (lists.size() == 1) return lists.back(); vector l; while (!lists.empty()) { if (lists.size() == 1) { l.push_back(lists.back()); lists.pop_back(); } else { ListNode *p = lists.back(); lists.pop_back(); ListNode *q = lists.back(); lists.pop_back(); l.push_back(merge(p, q)); } } return mergeKLists(l); } ListNode *merge(ListNode *p,ListNode *q) { ListNode fake(0); ListNode *m = &fake; while (p && q) { if (p->val < q->val) { m->next = p; p = p->next; } else { m->next = q; q = q->next; } m = m->next; } m->next = p ? p : q; return fake.next; } };