user6820297 user6820297 - 2 months ago 8
C++ Question

segment fault in single function mergesort of linked list

I am running into a segmentation fault from using the online C++ compiler while doing this single function mergesort all day and I couldn't locate where it possibly be. The other problem is that the way that I don't understand this method of finding the mid of the linked list, why is it assignment operator, is there a better way to do it? Any help will be appreciated.

#include <stdio.h>
#include <stdlib.h>

struct listnode { struct listnode * next; int key; };

struct listnode * sort(struct listnode * a)
{
struct listnode *fast, *slow, *mid, *left, *right;
fast = a; left = a; right = NULL; mid = NULL;

//data is null or one node
if (!a || !a->next)
{
return a;
}

//find mid by declaring a pointer skipping throw an extra node for each loop

while (fast)
{
if (fast = fast->next) { fast = fast->next; }
mid = slow;
slow = slow->next;
}

//split the list in recursion
if (mid != NULL) { mid->next = NULL; }

a = sort(a); slow = sort(slow);

//merge
while (left != NULL && slow != NULL)
{
if (left->key < right->key) { left->next = mid; right = left; }
else
{
if (!right)
a = slow;
else
{
right = slow; right->next = slow; slow = slow->next; right->next = left;
}
}

}
if (left == NULL) { right->next = slow; }
return(a);

}


//test


int main()
{
long i;
struct listnode *node, *tmpnode, *space;
space = (struct listnode *) malloc(500000 * sizeof(struct listnode));
for (i = 0; i< 500000; i++)
{
(space + i)->key = 2 * ((17 * i) % 500000);
(space + i)->next = space + (i + 1);
}
(space + 499999)->next = NULL;
node = space;
printf("\n prepared list, now starting sort\n");
node = sort(node);
printf("\n checking sorted list\n");
for (i = 0; i < 500000; i++)
{
if (node == NULL)
{
printf("List ended early\n"); exit(0);
}
if (node->key != 2 * i)
{
printf("Node contains wrong value\n"); exit(0);
}
node = node->next;
}
printf("Sort successful\n");
exit(0);
}

Answer

At least one problem is:

while (fast)
{
    if (fast = fast->next) { fast = fast->next; }
    mid = slow;
    slow = slow->next; // <-------- HERE!
}

fast was assigned to non-null value before this loop, so control enters the loop and tries to read slow->next, which is invalid. The slow pointer was not assigned to anything before the loop, so it holds garbage value and does not point to valid memory location. Thus, reading memory by this pointer is very likely to violate process address space. And from the language perspective, reading an uninitialized pointer is an example of undefined behavior.

See also a good explanation in this question.