Home > Software engineering >  Merge several linked lists (smth with memory)
Merge several linked lists (smth with memory)

Time:11-04

I've made my own linked list and now I am trying to implement function which will merge all lists. However, unfortunately I get this error: "linkedList(28488,0x102a88580) malloc: *** error for object 0x600003a70010: pointer being freed was not allocated linkedList(28488,0x102a88580) malloc: *** set a breakpoint in malloc_error_break to debug"

I suppose that problem is in the main function, when I create a list in for-loop. I tried to make a new node using new operator and then make a list from this node, error message disappeared but program didn't work still.

Here is the input:

4

1--->4--->5

1--->3--->4

2--->6

1

Here is the output:

1--->1--->1--->2--->3--->4--->4--->5--->6

Here is the code:

struct Node
{
    int val;
    Node* next;
    Node(){}
    Node(int x) : val(x), next(nullptr){}
};

struct List
{
    List(Node* node) : head(node){}
    List() : head(nullptr){}
    ~List();
    void clear();
    void push_back(int key);
    void print();
    Node* head;
};

void List::push_back(int val)
{
    Node* newNode = new Node(val);
    Node* cur = head;
    if (head != nullptr)
    {
        while(cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newNode;
    }
    else
    {
        head = newNode;
    }
}

void List::print()
{
    Node* cur = head;
    while(cur != nullptr)
    {
        std::cout << cur->val;
        if (cur->next != nullptr)
        {
            std::cout << "--->";
        }
        cur = cur->next;
    }
}

void List::clear()
{
    Node* cur = head;
    while (cur != nullptr)
    {
        Node* a = cur;
        cur = cur->next;
        delete a;
    }
}

List::~List()
{
    clear();
}

Node* merge(Node* nodeFirst, Node* nodeSecond)
{
//function to merge two lists
    if (!nodeFirst)
    {
        return nodeSecond;
    }

    if (!nodeSecond)
    {
        return nodeFirst;
    }

    if (nodeFirst->val <= nodeSecond->val)
    {
        nodeFirst->next = merge(nodeFirst->next, nodeSecond);
        return nodeFirst;
    }
    else
    {
        nodeSecond->next = merge(nodeSecond->next, nodeFirst);
        return nodeSecond;
    }
}

Node* mergeAll(std::vector<List>& vecOfLists)
{
    Node* answer = vecOfLists[0].head;
    for (int i = 1; i < vecOfLists.size();   i)
    {
        answer = merge(answer, vecOfLists.at(i).head);
        vecOfLists.at(i).clear();
    }
    return answer;
}

std::vector<int> getNums(const std::string& s, std::vector<int>& numbers)
{
    size_t num_start = 0, num_end = 0;
    const std::string arrow = "--->";
    while (num_end < s.size())
    {
        num_end = s.find(arrow, num_start);
        if (num_end == std::string::npos)
        {
            num_end = s.size();
        }
        numbers.push_back(std::stoi(s.substr(num_start, num_end - num_start)));
        num_start = num_end   arrow.size();
    }
    return numbers;
}

List& makeList(List& list, const std::vector<int>& nums)
{
    for (const int& x : nums)
    {
        list.push_back(x);
    }
    return list;
}

int main()
{
    int k = 0;
    std::cin >> k;
    std::vector<List> vecOfLists;
    for (int i = 0; i < k;   i)
    {
         std::string s;
         std::cin >> s;

         std::vector<int> nums;
         getNums(s, nums);
         List list;
         makeList(list, nums);

         vecOfLists.push_back(list);
    }
    List list(mergeAll(vecOfLists));
    list.print();
}

CodePudding user response:

issue is here

    List list;
    makeList(list, nums);

    vecOfLists.push_back(list);

list will be destructed after that push_back and hence delete all its allocated nodes, but then when you exit main the destructor is called again for the copy of List head in that vector.

YOu need to make the copy operation (used by the vector push_back) smarter

  • Related