Merging two sorted linked list algorithm not working when using for loop-CodePudding

So in my following code, I have two lists. Each of them should be sorted in increasing order and then merged together into one list with SortedMerge(). The code works just fine when in the main I insert the numbers separately:

int main()
{
    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);

    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

But in my case I don't want to insert numbers separately but rather have two arrays and insert them to the list using for loop. The code again merges them together, but does not sort them in increasing order:

int main()
{
    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);

    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

The following code has both insert separately and with for loop. If for clarity anybody will need the overall code:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
struct Node
{
    int data;
    struct Node *next;
};
 
void MoveNode(struct Node **destRef, struct Node **source);
 
struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;
    struct Node **lastPointer = &result;
   
    while (1) {
        if (a == NULL) {
            *lastPointer = b;
            break;
        }
        else if (b == NULL) {
            *lastPointer = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(lastPointer, &a);
        else
            MoveNode(lastPointer, &b);
    
        lastPointer = &((*lastPointer)->next);
    }
    return (result);
}
 
void MoveNode(struct Node **destRef, struct Node **source)
{
    struct Node *newNode = *source;
    assert(newNode != NULL);
 
    *source = newNode->next;
    newNode->next = *destRef;
    *destRef = newNode; 
}

void insert(struct Node **head, int data)
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    if (newNode == NULL)
        printf(" Memory can not be allocated.");
    else {
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
    }
}

void printList(struct Node *node)
{
    while (node)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
int main()
{
    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);
    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);
    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

CodePudding user response：

The problem is the lists are not sorted in increasing order. You insert the elements from the last to the first in the arrays, but the contents of the arrays in already in decreasing order so you effectively get the list sorted in decreasing order. Then you prepend more elements, so these lists are unsorted.

change the insertion loop to for (int i = 0; i < n1; i ) insert(&a, list1[i]); and do not insert more elements or
change the array contents so the arrays are in increasing order or
change the insert function to insert the new node in the proper place.

Here is a modified version:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
void MoveNode(struct Node **destRef, struct Node **source)
{
    struct Node *newNode = *source;
    assert(newNode != NULL);
 
    *source = newNode->next;
    newNode->next = *destRef;
    *destRef = newNode; 
}

struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;
    struct Node **lastPointer = &result;
   
    for (;;) {
        if (a == NULL) {
            *lastPointer = b;
            break;
        }
        if (b == NULL) {
            *lastPointer = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(lastPointer, &a);
        else
            MoveNode(lastPointer, &b);
    
        lastPointer = &(*lastPointer)->next;
    }
    return result;
}
 
void insert(struct Node **head, int data)
{
    struct Node *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory cannot be allocated.\n");
        return;
    }
    while (*head != NULL && (*head)->data < data) {
        head = &(*head)->next;
    }
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void printList(const struct Node *node)
{
    while (node) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
 
int main()
{
    int list1[] = { 5, 10, 15 };
    int list2[] = { 2, 3, 20 };

    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = 0; i < n1; i  )
        insert(&a, list1[i]);
    for (int i = 0; i < n2; i  )
        insert(&b, list2[i]);

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);
    struct Node *final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

CodePudding user response：

Your SortedMerge function expects two lists sorted in ascending order and merges them into a single list in ascending order.

For the first example:

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);

(Note: insert inserts at the front of the list.)

List a: 5, 10, 15.
List b: 2, 3, 20

Lists a and b are in ascending order so are valid for SortedMerge.

For the second example:

    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);

(Note: insert inserts at the front of the list.)

List a: 15, 10, 5
List b: 20, 3, 2

Lists a and b are in descending order so are not valid for SortedMerge.

For the third (combined example):

List a: 5, 10, 15, 15, 10, 5
List b: 2, 3, 20, 20, 3, 2

Lists a and b are not sorted so are not valid for SortedMerge.