题目介绍
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
1 | Input: |
2 | [ |
3 | 1->4->5, |
4 | 1->3->4, |
5 | 2->6 |
6 | ] |
7 | Output: 1->1->2->3->4->4->5->6 |
解
1 | /** |
2 | * Definition for singly-linked list. |
3 | * struct ListNode { |
4 | * int val; |
5 | * ListNode *next; |
6 | * ListNode(int x) : val(x), next(NULL) {} |
7 | * }; |
8 | */ |
9 | class Solution { |
10 | private: |
11 | void mergeTwoLists(vector<ListNode*>& lists, vector<ListNode*>& lists2, int left, int right) { |
12 | ListNode* l1 = lists[left]; |
13 | ListNode* l2 = lists[right]; |
14 | ListNode first(0); |
15 | ListNode* pre = &first; |
16 | while (l1 != NULL && l2 != NULL) { |
17 | if (l2->val < l1->val) { |
18 | pre->next = l2; |
19 | pre = pre->next; |
20 | l2 = l2->next; |
21 | } else { |
22 | pre->next = l1; |
23 | pre = pre->next; |
24 | l1 = l1->next; |
25 | } |
26 | } |
27 | if (l1 != NULL) { |
28 | pre->next = l1; |
29 | } |
30 | if (l2 != NULL) { |
31 | pre->next = l2; |
32 | } |
33 | lists2.emplace_back(first.next); |
34 | } |
35 | public: |
36 | ListNode* mergeKLists(vector<ListNode*>& lists) { |
37 | if (lists.size() == 1) { |
38 | return lists[0]; |
39 | } else if (lists.size() == 0) { |
40 | return NULL; |
41 | } |
42 | vector<ListNode*> lists2; |
43 | int right = lists.size() - 1; |
44 | for (int left = 0; left <= right; left++) { |
45 | if (left == right) { |
46 | lists2.emplace_back(lists[left]); |
47 | } else { |
48 | mergeTwoLists(lists, lists2, left, right); |
49 | } |
50 | right--; |
51 | } |
52 | ListNode* ret = mergeKLists(lists2); |
53 | return ret; |
54 | } |
55 | }; |
Runtime: 24 ms
Memory Usage: 11.3 MB
