I am having problems with merge sorting a linked list. For some reason, some of the nodes keep getting disconnected from the list. The main problem seems to be coming from multiple conditional jumps since lists such as 1 4 2 3 are sorted, albeit with 6 conditional jumps, while 4 2 3 1 loses all nodes except the one holding the value 4. My code is based off of the code from tutorialspoint.com.
class Node {
public:
int val;
Node *next;
};
class Linked_list {
private:
unsigned int length;
Node *head;
//desc: sorts in ascending order then merges two linked lists
//param: Node*, the lists being sorted
Node* Linked_List::merge_lists_ascend(Node* ll1, Node* ll2) { //function for merging two sorted list
Node* newhead = NULL;
if(ll1 == NULL)
return ll2;
if(ll2 == NULL)
return ll1;
//recursively merge the lists
if(ll1 -> val <= ll2 -> val) {
newhead = ll1;
newhead -> next = merge_lists_ascend(ll1->next,ll2);
}
else {
newhead = ll2;
newhead -> next = merge_lists_ascend(ll1,ll2->next);
}
return newhead;
}
//desc: splits a linked list into two lists
//param: Node*, the list being split; Node**, the two lists that will be filled
//by the split list
void Linked_List::splitList(Node* start, Node** ll1, Node** ll2) {
Node* slow = start;
Node* fast = start -> next;
while(fast != NULL) {
fast = fast -> next;
if(fast != NULL) {
slow = slow -> next;
fast = fast -> next;
}
}
*ll1 = start;
*ll2 = slow -> next;
//spliting
slow -> next = NULL;
}
//desc: recursive function that runs through the splitting, sorting and merging
//param: Node**, the starting node
Node* Linked_List::merge_sort_ascend(Node* start) {
Node* head = start;
Node* ll1;
Node* ll2;
//base case
if(head == NULL || head->next == NULL) {
return head;
}
splitList(head,&ll1,&ll2); //split the list in two halves
//sort left and right sublists
merge_sort_ascend(ll1);
merge_sort_ascend(ll2);
//merge two sorted list
start = merge_lists_ascend(ll1,ll2);
return start;
}
Aucun commentaire:
Enregistrer un commentaire