c++ - 合并 K 排序列表中大小 2 列表的错误

Question

我正在解决 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) 或者 eg.(1->2 and 3->4) 它分别返回 0->2 和 0->2->3->4 。 (我知道这有一个糟糕的时间复杂度)

Answer 1

您的代码的问题在于您返回的列表包含指向已被销毁的节点的指针。所以你的代码有未定义的行为。

ListNode* Solution::mergeKLists(vector<ListNode*> &A) {
    vector<ListNode> m; // this vector contains the nodes of your merged list
    ...
    ListNode* k = &m[0]; // here you take a pointer to the content of m
    ...
        m[i].next = &m[i+1]; // here you make another pointer to the contents of m
    ...
    return k; // here you return that pointer
} // but here m is destroyed

因此最终结果是您返回一个指向 vector 的指针，该 vector 在函数退出时已被销毁。对该指针的任何后续使用都是未定义的行为。