Merge sort a Linked list (segementation fault)

Question

The below code is for merge sorting a linked list. Its giving out a segmentation fault. I really dont know how to deal with the above. All I could find was that I was trying to access a restricted part of the memory, the only place I think i could've gone wrong is re combining the two linked lists after splitting and sorting them under the split function body. I'd appreciate if I could get some guidance on how to deal with segmentation faults from here on & how to rectify them.

//Segmentation fault
#include <iostream>
using namespace std;
class Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};

void print(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

Node *insert()
{
    int data;
    cin >> data;
    Node *head = NULL;
    Node *tail = NULL;
    while (data != -1)
    {
        Node *n = new Node(data);
        if (head == NULL)
        {
            head = n;
            tail = n;
        }
        else
        {
            tail->next = n;
            tail = tail->next;
        }
        cin >> data;
    }
    return head;
}

Node *sortedMerge(Node *h1, Node *h2)
{
    // Node *fHead = NULL;
    // Node *fTail = NULL;

    if (!h1)
    {
        return h2;
    }

    if (!h2)
    {
        return h1;
    }

    if (h1->data < h2->data)
    {
        h1->next = sortedMerge(h1->next, h2);
        return h1;
    }

    else
    {
        h2->next = sortedMerge(h1, h2->next);
        return h2;
    }
}

void split(Node *head, Node *h1, Node *h2)
{

    Node *slow = head;
    Node *fast = head->next;
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }
    h1 = head;
    h2 = slow->next;
    slow->next = NULL;
    
}

void mergeSort_LL(Node *head)
{
    Node *temp = head;
    Node *h1;
    Node *h2;

    if ((temp == NULL) || (temp->next == NULL))
    {
        return;
    }

    split(temp, h1, h2);

    mergeSort_LL(h1);
    mergeSort_LL(h2);

    head = sortedMerge(h1, h2);
}

int main()
{
    Node *head = insert();
    print(head);
    cout << endl;

    mergeSort_LL(head);
    cout << "Sorted List is : " << endl;
    print(head);
    return 0;
}

Learn to use `gdb`. This might help https://stackoverflow.com/questions/2876357/determine-the-line-of-code-that-causes-a-segmentation-fault — Aditya Singh Rathore, Apr 20 '21 at 19:05
I did, i even tried the inbuilt vs code one. the while loop inside the split func body is the area of concern i tried a few different ways of the fast and slow pointer method to find the median of the linked list but little to no avail. — Dcypher., Apr 20 '21 at 19:08
Have you tried changing the 2 pointer method, to see if the fault gets fixed? — Abhinav Mathur, Apr 20 '21 at 19:10
`split` should get a *reference* to the h1 and h2 pointers, otherwise the caller will not get those altered back. — trincot, Apr 20 '21 at 19:11
@AbhinavMathur The approach is available online hence why i tried my approach of solving the said problem. — Dcypher., Apr 20 '21 at 19:13
@trincot But they're already dynamically allocated. Please correct me with a code snippet if wrong I'm kinda new. — Dcypher., Apr 20 '21 at 19:14
You should declare those two parameters with double `*`, and the caller should do `split(temp, &h1, &h2)` — trincot, Apr 20 '21 at 19:15
@trincot i understood what you're trying to say. I'll be implementing that. Is there no way the above code will work unless double pointers are used? — Dcypher., Apr 20 '21 at 19:19
If you use a single pointer, then the change that the function makes to that variable will not be visible to the caller. The caller must pass the memory location of the pointer, so the function will modify the caller's pointer. — trincot, Apr 20 '21 at 19:20
@trincot I understood the concept now! Thanks for your time and efforts everyone! — Dcypher., Apr 20 '21 at 19:27

trincot · Accepted Answer · 2021-04-20T21:17:22.117

Your call to split will not make h1 or h2 get a value. Arguments are passed by value. Since you evidently need h1 and h2 to get a different value from that split call, you should pass their addresses:

 split(temp, &h1, &h2)

The function itself should therefore accept these addresses instead of the node pointers themselves:

void split(Node *head, Node **h1, Node **h2) {
    // ...
    *h1 = head;
    *h2 = slow->next;
    // ...
}

Merge sort a Linked list (segementation fault)

1 Answers1