I wrote a program to merge two sorted linked list into one and this function was the one I used to do it but it's not working. The code of the function is as follows is as follows:

void combine(Node **temp, Node *temp_1, Node *temp_2){
   while(temp_1 != NULL || temp_2 != NULL){
      if(temp_1->data > temp_2->data){
         push(temp, temp_2->data);
         temp_2 = temp_2->next;
      }
      else{
         push(temp, temp_1->data);
         temp_1 = temp_1->next;
      }
   }
   while(temp_1 != NULL){
      push(temp, temp_1->data);
      temp_1 = temp_1->next;
   }
   while(temp_2 != NULL){
      push(temp, temp_2->data);
      temp_2 = temp_2->next;
   }
}

Now, this code doesn't add anything to the final linked list. If I write something like

push(temp, temp_1->data);

it will add elements just fine so the problem isn't definitely with the push function. Can someone tell me what is the problem with the above code?

The full code is in the following URL: https://ide.geeksforgeeks.org/FZ8IS4PADE

CodePudding user response：

The issue is the while condition:

while(temp_1 != NULL || temp_2 != NULL){

This will allow the execution of the body of the loop when just one of those two pointers is null, and this will result in undefined behaviour on the first statement in that body:

    if(temp_1->data > temp_2->data){

The || should be an &&. This will fix your issue.

Other remarks on your code

• Don't use NULL for comparing your pointer variables against, but nullptr

• The use of push makes your code inefficient: at every push, your code is starting an iteration through the whole list to find the end of it. Since you actually know what is the last node (since it was created in the previous iteration of the loop) this is a waste of time. Instead, keep a reference to the tail of the list that is being created. As there is no tail at the start of the combine process, it might be useful to create a "sentinel" node that comes before the real list that will be returned.

• Use better variable names. temp is not temporary at all. It is the result that the caller wants to get: this name is misleading.

• Avoid code repetition. The last two loops are the same except for the list that is copied from, and this code is again similar to the parts in the main loop. So create a function that does this job of copying a node from a source list to the end of another list, and that advances both pointers.

Here is what that would look like:

void copyNode(Node **source, Node **targetTail) {
   *targetTail = (*targetTail)->next = new Node((*source)->data);
   *source = (*source)->next;
}

void combine(Node **result, Node *head_1, Node *head_2){
   Node *sentinel = new Node(0); // Dummy 
   Node *current = sentinel;
   while(head_1 != nullptr && head_2 != nullptr){
      if(head_1->data > head_2->data){
         copyNode(&head_2, &current);
      }
      else{
         copyNode(&head_1, &current);
      }
   }
   if (head_1 == nullptr) {
      head_1 = head_2;
   }
   while (head_1 != NULL) {
      copyNode(&head_1, &current);
   }
   *result = sentinel->next;
   delete sentinel; 
}