0

In this code, I am trying to implement mergeSort in a Linked list. My sample input 1 23 5 6 8 5 48 5 8 65 -1. but after program completion, it does not show any output neither address of the sorted linked list nor the whole linked list. I think my list is lost in the mergeSort function. but I don't know where. Sorry for the question asking format of mine, I am a new bee here.

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

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

//print data of Linked List.
void print(Node *head ){
        Node *temp = head ;
        while( temp!= NULL ){
            cout << temp->data << "  " ;
            temp = temp->next ;

        }

    }

Node* MidNode(Node* head){
    Node *fast = head->next ;
    Node *slow  = head ;
    while(fast->next != NULL || fast != NULL){
        slow = slow->next;
        fast = fast->next;
        fast = fast->next;
    }
    return slow;
}
Node* mergeLL(Node *h1 , Node *h2){
    Node *head = NULL , *tail = NULL;
    if(h1->data < h2->data) {
        head = h1 ;
        tail = h1;
        h1 = h1->next;
    }
    else {
        head = h2 ;
        tail = h2 ;
        h2 = h2->next;
    }
    while (h1 != NULL and h2 != NULL){
        if(h1->data > h2->data){
            tail->next = h2;
            tail = tail->next;
            h2 = h2->next;
        }
        else {
            tail->next = h1 ;
            tail = tail->next ;
            h1 = h1->next;
        }
        
    }
        while( h2 != NULL){
            tail->next = h2 ;
            tail = tail->next;
            h2 = h2->next;
        }
        while( h1 != NULL ){
            tail->next = h1 ;
            tail = tail->next;
            h1 = h1->next;
        }
        return head ;
}


Node* mergeSort(Node *head ){
    if(head == NULL || head->next == NULL) return head  ;
    Node *mid = MidNode(head);
    Node *leftList = head;
    Node *rightList = mid->next ;
    mid->next = NULL ;
    leftList = mergeSort(leftList);
    rightList = mergeSort(rightList);
    return mergeLL(leftList , rightList);
    
}



int main(){
    Node* head2 = takeInput();
    
    Node* ans = mergeSort(head2 );    
    cout << ans <<endl;
    print(ans);
    return 0 ;
}
4
  • 1
    What is sample input? Commented Dec 4, 2021 at 6:41
  • Make it easier on yourself to debug this. Don't take input from the user; for testing, your takeInput() function should be a series of statements like insert(23); where insert() is a new function (with code ripped from the current takeInput()) responsible solely for inserting a value into your list. (It was a bad design decision to make one function responsible for both collecting input and inserting that data into the list.) Also, don't deal with 10 nodes if 2 or even 1 node is enough to reproduce the issue. This should be simple enough to step through in a debugger. Commented Dec 4, 2021 at 7:07
  • @JaMiT , its working after taking input one by one without using the input function. But I want to know whats wrong with input function which cause mergeSort function function to now work. Commented Dec 4, 2021 at 8:00
  • @Amitkhurrana That suggests that your error is in the input function rather than in the sort, but maybe symptoms do not manifest right away. So you should build one list without using the input function and one with using the input function (same data in each case) and carefully compare the two to see where they differ. Commented Dec 4, 2021 at 8:11

1 Answer 1

1

In the MidNode function you have:

while(fast->next != NULL || fast != NULL){
    //...
}

What if fast is NULL? You dereference NULL pointer and get into the UB realm.

You probably meant: while(fast != NULL && fast->next != NULL). Note that even operation is not correct in your code.

Next, inside this loop:

        slow = slow->next;
        fast = fast->next;
        fast = fast->next;

Here you have a chance to get UB again for the same reason. You need to add the check:

        slow = slow->next;
        fast = fast->next;
        if (fast != NULL)
            fast = fast->next;

I haven't checked the rest of the code, so probably there are more issues.

Sign up to request clarification or add additional context in comments.

3 Comments

I tried your code but it still not working
Well, that ends this question then, because I did the same and it works fine.
@Amitkhurrana, you have more issues in your code, but this is not a "free service for solving homework tasks". Be specific, ask concrete questions, and good luck in debugging.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.