Merge two sorted linked lists doesnt push all valus-CodePudding

Im tring to learn basic data structures & algorithms. I have a problem with merging two sorted doubly linked lists.I have no idea why the last value doesnt push to merged list.

As results for now for my code i get this.

Left List: [(1)(3)(5)]

Right List: [(-1)(2)(10)(20)]

Merged: [(-1)(1)(2)(3)(5)(10)]

Expected: [(-1)(1)(2)(3)(5)(10)(20)]

template <typename T>
LinkedList<T> LinkedList<T>::merge(const LinkedList<T> &other) const
{

  LinkedList<T> left = *this;
  LinkedList<T> right = other;

  LinkedList<T> merged;

  Node * lptr = left.head_;
  Node * rptr = right.head_;

  while (lptr != NULL && rptr !=NULL) {
    if(lptr->data <= rptr->data){
      merged.pushBack(lptr->data);
      lptr = lptr->next;
    }else{
      merged.pushBack(rptr->data);
      rptr = rptr->next;
    }
    if(lptr == NULL && rptr != NULL){
      merged.pushBack(rptr->data);
      rptr = rptr->next;

    }else{
      merged.pushBack(lptr->data);
      lptr = lptr->next;
    }
  }

return merged;
}

CodePudding user response：

For these lists

Left List: [(1)(3)(5)]

Right List: [(-1)(2)(10)(20)]

when the left list achieves a null pointer the right list yet contains two nodes with values 10 and 20.

However you are appending only one node

if(lptr == NULL && rptr != NULL){
  merged.pushBack(rptr->data);
  rptr = rptr->next;

}else{    if(lptr == NULL && rptr != NULL){
//..

Also pay attention to that the negation of the condition

lptr == NULL && rptr != NULL

looks like

!( lptr == NULL && rptr != NULL )

that is the same as

( lptr != NULL || rptr == NULL )

So you may not use in this if statement just the else part.

Remove this code snippet from the while loop and write two additional while loops like

  while (lptr != NULL && rptr !=NULL) {
    if(lptr->data <= rptr->data){
      merged.pushBack(lptr->data);
      lptr = lptr->next;
    }else{
      merged.pushBack(rptr->data);
      rptr = rptr->next;
    }
  }

  while (lptr != NULL ){
    merged.pushBack(lptr->data);
    lptr = lptr->next;
  }

  while (rptr != NULL ){
    merged.pushBack(rptr->data);
    rptr = rptr->next;
  }

There is also one more drawback. In these records

  LinkedList<T> left = *this;
  LinkedList<T> right = other;

there is used the copy constructor that can results either in undefined behavior or in creating new lists that is inefficient.

So remove these records and just write

  Node * lptr = this->head_;
  Node * rptr = other.head_;

So the function will look like

template <typename T>
LinkedList<T> LinkedList<T>::merge(const LinkedList<T> &other) const
{
    LinkedList<T> merged;

    Node * lptr = this->head_;
    Node * rptr = other.head_;

    while (lptr != NULL && rptr !=NULL) {
      if(lptr->data <= rptr->data){
        merged.pushBack(lptr->data);
        lptr = lptr->next;
      }else{
        merged.pushBack(rptr->data);
        rptr = rptr->next;
      }
    }

    while ( lptr != NULL ){
      merged.pushBack(lptr->data);
      lptr = lptr->next;
    }

    while ( rptr != NULL ){
      merged.pushBack(rptr->data);
      rptr = rptr->next;
    }

    return merged;
}