Merge Sorted Linked Lists with head node

Question

I am writing a void function void merged_lists (cell * l1, cell * l2, cell * l3); who receives two linked lists, headed by l1 and l2, whose content is ordered in non-decreasing order, and generate a new list headed by l3 that contains the elements of l1 and l2 ordered.

If the list headed by l1 is l1 -> 1 -> 7 -> 9 -> 10 -> NULL and headed by l2 is l2 -> 2 -> 3 -> 8 -> NULL, for example, the output must be l3 -> 1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> NULL

typedef struct node {
    int data;
    struct node *next;
} node;

void display (node *le){

    node *p = le->next;

    while(p != NULL ){
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");

}

void MergeLists(node *l1, node *l2, node *l3) {
  if (!l1) 
    l3 = l2;
  if (!l2) 
  l3 = l1;

    //Chosing head of merged list
  if (l1->data < l2->data) {
    l3->next= l1;
  } else {
    l3 = l2;
    l2 = l1;
    l1 = l3;
  }

  while(l1->next && l2->next) {
    if (l1->next->data > l2->data) {
    //Step 1. Save the next pointer
      node *tmp = l1->data;
    //Step 2. Change next pointer to point L2
      l1->next = l2;
    //Step 3. Move L2 to temp
      l2 = tmp;
    }
    //Step 4. Move L1 ahead
    l1 = l1->next;
  } 
  if (!l1->next) l1->next = l2;
  display(l3);
}

My output for l1->1->7->9->10->11 and l2->2->3->3->8 is 0 -> 1 -> 2 -> 3 -> 3 -> 7 -> 9 -> 10 -> 11 -> NULL.

Any tips on how to solve this problem at the beginning?

(I know I posted a similar question earlier, but as the focus changed, I thought it was fair to do another post)

Answer 1

As mentioned in this answer, l1 inside the function MergeLists points to the start of a linked list but l1 is local to MergeLists.

Changes done on l1 or l2 or l3 will not be reflected in the caller module.

You need to pass a pointer to pointer (sometimes called a 'double pointer' but that's ambiguous with double *) to reflect on caller function.

Here is the snippet without allocating extra memory nodes are merged,

void MergeLists(node *l1, node *l2, node **l3) {
    if (!l1) {
        *l3 = l2;
        return; //no mearge required
    }else if (!l2){
        *l3 = l1; //no mearge required
        return;
    }

    node tempHead;
    node*tempPtr = &tempHead;

    while (l1 && l2) {

        if (l1->data < l2->data)
        {
            tempPtr->next = l1;
            l1 = l1->next;
        }
        else {
            tempPtr->next = l2;
            l2 = l2->next;
        }
        tempPtr = tempPtr->next;
    }

    if (!l1)
        tempPtr->next = l2; //l1 is empty remaining l2 is appended to the merged list
    else
        tempPtr->next = l1; //l2 is empty remaining l1 is appended to the merged list
    *l3 = tempHead.next; // temporary head is copied back to the caller
}

which should be called like MergeLists(l1, l2, &l3); but make sure that l1,l2 will no more pointing to the initial list.

You can find complete code here.

Answer 2

There is a first problem with this code

if (!l1) 
    l3 = l2;
if (!l2) 
    l3 = l1;

You override l3 with the value of l2 or l1. The result is a memory leak because the head node l3 was referring to has no more references.

If the caller had a reference on the head node of l3 he will still see an empty list after the call because the head node of l3 has not been modified.

You should copy all the nodes of l1 or l2 into l3 so that l1 and l2 are left unmodified and l3 is a copy of one of them.

There is also a problem with this code

//Chosing head of merged list
if (l1->data < l2->data) {
    l3->next= l1;
} else {
    l3 = l2;
    l2 = l1;
    l1 = l3;
}

You assign to l3->next the head node of l1. This means that the first node after the head node of l3 is the head node of l1. Since the head node does not contain a relevant value, this yields a wrong result.

Another problem is in the else block. Again, you override the value of l3 and thus loose the reference to the head node of l3. The caller of the MergeLists function won’t see a change in l3. It will still be an empty list after the call.

Another problem is that the following line won’t compile. Did you really compile and run your program ? l1->data is of type int, not of type node*.

node *tmp = l1->data;

I stopped reading your code here because it didn’t made sense.

The correct code is as simple as this

void MergeLists(node *l1, node *l2, node *l3) {
    node *l1p = l1->next, *l2p = l2->next, l3p = l3;
    while (l1p != NULL || l2p != NULL) {
        if (l1p != NULL && (l2p == NULL || l1p->data < l2p->data)) {
            l3p->next = malloc(sizeof(node));
            l3p = l3p->next;
            l3p->next = NULL;
            l3p->data = l1p->data;
            l1p = l1p->next;
        } else {
            l3p->next = malloc(sizeof(node));
            l3p = l3p->next;
            l3p->next = NULL;
            l3p->data = l2p->data;
            l2p = l2p->next;
        }
    }
}

This code assumes that l3->next == NULL when starting executing the function.