sorting - Merge sort two linked list into a third linked list via recursion - c++ -

sorting - Merge sort two linked list into a third linked list via recursion - c++ -

so basically, have merge 2 linked lists (passed parameters) 3rd linked list (also passed in parameter) - end of function new list must still sorted , other linked lists must empty. i'm pretty sure i'm close, reason don't think 3rd list beingness computed correctly. if take , tell me i'm wrong real quick awesome, considering i'm not @ recursion. end, headx , heady should both empty, of items sorted in headz. however, after function done, headz not right (though i'm not sure why).

void sortedmergerecur(node* &headx, node* &heady, node* &headz) { // can assume both headx , heady sorted linkedlists // first found base of operations case or when stop if((headx == 0) && (heady != 0)) { // x empty, y not headz = heady; heady = 0; return; } else if((heady == 0) && (headx != 0)) { // y empty, x not headz = headx; headx = 0; return; } else if((heady == 0) && (headx == 0)) { // if they're both empty, don't need add together z headz = 0; return; } // pick either x or y add together if (headx->data <= heady->data) { headz = headx; sortedmergerecur(headx->link, heady, headz->link); headx = 0; } else // if(headx->data > heady->data) { headz = heady; sortedmergerecur(headx, heady->link, headz->link); heady = 0; } return; }

update - need advance headx or heady during merge sort. empty lists checks can simplfied. illustration seems work:

void sortedmergerecur(node* &headx, node* &heady, node* &headz) { // assume both headx , heady sorted linkedlists // check empty lists if(headx == 0) { headz = heady; heady = 0; return; } if(heady == 0) { headz = headx; headx = 0; return; } // move smaller of x,y z if (headx->data <= heady->data) { headz = headx; headx = headx->link; sortedmergerecur(headx, heady, headz->link); } else { headz = heady; heady = heady->link; sortedmergerecur(headx, heady, headz->link); } return; }

c++ sorting recursion