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 ;
}
takeInput()function should be a series of statements likeinsert(23);whereinsert()is a new function (with code ripped from the currenttakeInput()) 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.