-1

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

Tanmay Sharma
  • 59
  • 8
  • 2
    *so the problem isn't definitely with the push function* -- Where do you think the problem is? If you don't know, then this is why you should use the [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to identify the problem spot. Now, *how* to fix the problem is different, as that may require "outside" help, but hopefully it won't once you identify where the problem is. – PaulMcKenzie Jan 04 '22 at 13:33
  • 2
    A [mre] would be really helpful. From first glance, shouldn't `while(temp_1 != NULL || temp_2 != NULL)` use `&&` instead of `||`? This can easily cause undefined behaviour. – Lukas-T Jan 04 '22 at 13:34
  • A few tangential comments. First, it's awesome you are learning C++. There are many good books and blogs out there to help you on your journey. Second, due to its long history and standardization changes, it can be hard to tell what is "modern" C++ without those books or blogs telling you as such (e.g., C++11, C++14, C++17, or C++20). With that in mind, I often find that the code on GeeksForGeeks is NOT modern C++ and does not follow good production-quality standards. The thing that jumps out most to me here is the use of `Node**` when modern C++ has smart pointers like `shared_ptr`. – AndyG Jan 04 '22 at 13:34
  • 1
    `while(temp_1 != NULL || temp_2 != NULL) {` --> `while(temp_1 && temp_2) {` -- Even with this, you should use `nullptr`, not `NULL`. – PaulMcKenzie Jan 04 '22 at 13:52

1 Answers1

1

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; 
}
trincot
  • 317,000
  • 35
  • 244
  • 286