Я решаю проблему на InterviewBit (ссылка): https://www.interviewbit.com/problems/merge-k-sorted-lists/ Мне нужно объединить k отсортированных связанных списков и вернуть их как один отсортированный список. Это мое решение:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
bool is(const ListNode& x, const ListNode& y) { return x.val < y.val; }
ListNode* Solution::mergeKLists(vector<ListNode*> &A) {
vector<ListNode> m;
for(int i=0;i<A.size();i++){
while(A[i]!=NULL){
m.push_back(*A[i]);
A[i]=A[i]->next;
}
}
sort(m.begin(),m.end(),is);
ListNode* k =&m[0];
for(int i=0;i<m.size()-1;i++){
m[i].next=&m[i+1];
}
m[m.size()-1].next=NULL;
return k;
}
Вы можете скопировать код и проверить с помощью любого пользовательского ввода, он работает, но возвращает неверный список, когда предоставляется только связанный список размера 2, например. (1-> 2) или, например, (1-> 2 и 3-> 4) он возвращает 0-> 2 и 0-> 2-> 3-> 4 соответственно. (Я знаю, что это имеет плохую временную сложность)
ListNodeнаходится в вектореm, а векторmявляется локальным для функции, и вы возвращаете указатель на содержимоеm. Но если ты не хочешь мне верить, это твой выбор. 03.08.2019m[0]. И, конечно же, все ваши следующие указатели также указывают на содержимоеm. Таким образом, все эти указатели становятся недействительными, как толькоmуничтожается, что происходит при выходе из функции. 03.08.2019A, поэтому в конце функцииAпросто будут пустые списки, потому что все узлы были перемещены в новый список. . 03.08.2019mнаvector<ListNode*> m;и удалять узлы сA[i], когда вы нажимаете их наm. 03.08.2019new), что было бы еще менее эффективным, чем то, что у вас есть в настоящее время. 03.08.2019