samedi 6 juin 2020

C++ Linked list merge sort keeps losing nodes

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