LeetCode | Merge k Sorted Lists
タイトル:
Merge
k
sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
構想:外ソートのようなアルゴリズムは、直接コードをつけましょう.
タイトル:
Merge
k
sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
構想:外ソートのようなアルゴリズムは、直接コードをつけましょう.
タイトル:
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int count = lists.size();
for(int i = 0; i < lists.size(); i++)
{
if(lists[i] == NULL)
{
count--;
}
}
ListNode * result = NULL;
ListNode * begin = NULL;
while(count > 0)
{
int minPos = -1;
for(int i = 0; i < lists.size(); i++)
{
if(minPos == -1 && lists[i] != NULL)
{
minPos = i;
}
else if(minPos != -1 && lists[i] != NULL)
{
minPos = lists[minPos]->val<lists[i]->val?minPos:i;
}
}
if(result == NULL)
{
result = lists[minPos];
begin = result;
}
else
{
result->next = lists[minPos];
result = result->next;
}
lists[minPos] = lists[minPos]->next;
if(lists[minPos] == NULL)
{
count--;
}
};
return begin;
}
};