I am having problem debugging this Merge Sort for LinkedList Problem

Question

I am trying to mergeSort two linked lists, and have used functions

mid - To find the midpoint of LL
merge - To merge the sorted linked lists
mergeSort - The final function is called recursively

Following is the class structure of the Node class:

class Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

My code:

Node *merge(Node *head1, Node *head2)
{
    Node *nh = NULL;
    Node *nt = NULL;
    
    if(head1==NULL)
    {
        return head2;
    }

    if(head2==NULL)
    {
        return head1;
    }

    if(head1->data<=head2->data)
    {
        nh = head1;
        nt = head1;
        head1 = head1->next;
    }
    else
    {
        nh = head2;
        nt = head2;
        head2 = head2->next;
    }
    
    while(head1!=NULL && head2!=NULL)
    {
        if(head1->data<=head2->data)
        {
            nt->next = head1;
            nt = head1;
            head1=head1->next;
        }
        else
        {
            nt->next = head2;
            nt = head2;
            head2 = head2->next;
        }
    }
    
    if(head1!=NULL)
    {
        nt->next =head1;
    }
    if(head2!=NULL)
    {
        nt->next =  head2;
    }
    return nh;
}


Node *mid(Node *head)
{
    if(head==NULL)
    {
        return head;
    }
    Node *fast = head;
    Node *slow = head;
    
    while(fast->next!=NULL && fast->next->next!=NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}


Node *mergeSort(Node *head)
{
    if(head==NULL)
    {
        return head;
    }
    Node *midpoint = mid(head);
    
    Node *half1 = head;
    Node *half2 = midpoint->next;
    midpoint->next = NULL;
    
    half1 = mergeSort(half1);
    half2 = mergeSort(half2);
    
    Node *mergeHead = merge(half1,half2);
    
    return mergeHead;
}

I am getting runtime errors. How can I get this to work?

Hi welcome to the forum. Please post up the runtime error that you are getting. — ChrisBD, Aug 04 '22 at 11:12
I recommend you put away your code for a while, and bring out a pencil and some paper. Draw two simple lists on the paper, using boxes for the nodes (or other variables), and arrows for the links (pointers in general). Then attempt to "implement" the merge sort by rearranging the pointers on paper, by erasing and redrawing arrows. Once you get this to work, you translate the set of operations into code. — Some programmer dude, Aug 04 '22 at 11:16
If the newly implemented code doesn't work, then use a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through the code statement by statement while monitoring variables and their values. At the same time trace all steps using a set of papers, again erasing and redrawing arrows as you modify them in the code. Does the code work as your original drawings? Do the new drawings make sense? If not then the code is wrong and needs to be rewritten. — Some programmer dude, Aug 04 '22 at 11:16
Once you have this working, you may want to consider a [bottom up merge sort for linked list](https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists), which is more efficient. I can add an answer with example code if interested. — rcgldr, Aug 04 '22 at 14:38
@Someprogrammerdude i tried implementing the pen-pencil method, and it really helps, thankyou so much for helping! — Ashvend, Aug 05 '22 at 07:21
@rcgldr I will try it definitely, right now, I am trying to reverse linked lists — Ashvend, Aug 05 '22 at 07:23

trincot · Accepted Answer · 2022-08-05T07:29:47.483

0

The problem is that your recursion does not stop. You have as base case that head is NULL, but what if head is a list with one element? Then the list will split into an empty list and a list with that one element. So there will be a next recursive call with that one element... which is what you already had, and so it continues until you run out of stack memory.

You need to also make that a base case, reasoning that a list of just one element is already sorted, and so you can just return it:

    if (head == NULL || head->next == NULL) // <---
    {
        return head;
    }

edited Aug 05 '22 at 07:29

answered Aug 04 '22 at 12:35

trincot

317,000
35
244
286

Hey! Thank you so much, this worked out perfectly, I didn't account for a linked list with single element. – Ashvend Aug 05 '22 at 07:19

I am having problem debugging this Merge Sort for LinkedList Problem

1 Answers1