How do I merge-sort a linked list in c++?

Question

Hi everyone sorry my question is really vague that wasn't my intention. Anyway I have been trying to use mergesort to sort a linked list in c++. Unfortunately I am getting an access violation error ill try to show my error using a screenshot. Any way here is my code. Can you please help me figure out whats wrong?.

this image shows the error I am getting

Here is my code:

#include <iostream>
#include <iomanip>    
#include <fstream>    
#include <stdlib.h>   
#include <string>

using namespace std;    

struct listNode
{   
    int  id, inv;
    listNode  *next;

    listNode(int tempId, int tempInv, listNode *nxt);
};

listNode::listNode(int tempId, int tempInv, listNode *nxt)
    : id(tempId), inv(tempInv), next(nxt)    
{       
    // all values initialized using initializer list
}   

void merge(listType &root, nodePtr &first, nodePtr &mid, nodePtr &last)
{    
    nodePtr index = root.first;   
    nodePtr index2 = mid->next;

    int num;

    nodePtr first2 = first;    
    nodePtr last2 = last;  
    nodePtr mid2 = mid;

    for (first2; first2->id <= last->id; first2 = first2->next)
    {   
        if (index->id > mid->id)
        {
            swap(first->id, index2->id);
            mid = mid->next;
            index2 = mid;

        }
        else if (index2->id > last->id)
        {
            swap(first->id, index->id);
            root.first = root.first->next;
            index = root.first->next;
        }
        else if (first->id < index->id)
        {
            swap(first->id, index->id);
            root.first = root.first->next;
            index = root.first->next;
        }
        else
        {
            swap(first->id, index2->id);
            mid = mid->next;
            index2 = mid;
        }
    }
}

void mergeSort(listType& root, nodePtr &first  , nodePtr &last )
{
    if (root.last->id - root.first->id == 0)
    {
    }
    else if (root.first->next == root.last)
    {
        if (root.last->id < root.first->id)
        {
            //int temp = root.first->id;
            swap(root.first->id, root.last->id);
            //swap();
        }
    }
    else
    {
        nodePtr first = root.first;
        int i = 0;
        for (root.first; root.first->id < root.last->id; root.first = root.first->next)
        {
            i++;
        }
        int mid = i / 2;
        nodePtr merger = first;
        nodePtr merger2;
        root.first = first;
        for (int r = 0; r < mid; r++)
        {
            root.first = root.first->next;
            merger = root.first;
        }

        mergeSort(root, root.first, merger);
        merger2 = root.first->next;
        mergeSort(root, merger2, root.last);
        merge(root, root.first, merger, root.last);
    }
}

Sorry this is being shown horribly this is my first time trying to post something like this i have tried doing this stuff before but it never works well. Sorry

Thomas · Answer 1 · 2016-04-14T19:42:32.367

0

The answer is in your screenshot. You are here:

for (first2; first2->id <= last->id; first2 = first2->next)

executing

first2->id

and

first2 is null

One solution it to check pointer validity before accessing

for ( ; first2 && first2->id <= last->id; first2 = first2->next)

edited Apr 14 '16 at 19:42

answered Apr 14 '16 at 19:30

Thomas

4,980
2
15
30

Actually, I think the check for `first2->id` against `last->id` is redundant if you're checking if `first2` is `NULL`. – ebyrob Apr 14 '16 at 19:33
didn'check that much, `first != last`seems sufficient – Thomas Apr 14 '16 at 19:34
Creeping elegance, I think the OP wants to iterate over the last node, not skip it. – ebyrob Apr 14 '16 at 19:36

How do I merge-sort a linked list in c++?

1 Answers1