Trying to merge a linked list in descending order

Question

So I have two linked lists with my own Node implementation being the Linked list. For some reason I have the code that merges both lists in place that should add the least value and then move down both lists, consistently checking which one is least and adding it to the new list. For some reason my code merges both lists but not in ascending order.

/*
Takes two lists and merges them without creating extra nodes. */
Node *merge(Node* list1, Node* list2) {
    Node *mergelist, *cur1, *cur2, *curm, *prevm;

    cur1 = list1, cur2 = list2;
    mergelist = NULL;

    while (cur1 != NULL || cur2 != NULL) {
        // List2:node < List1:node
        if (cur1 != NULL && cur2 != NULL && cur2->value < cur1->value) {
            curm = cur2;
            cur2 = cur2->next;
            curm->next = NULL;
        }

        // List2:node <= List1:node
        else if (cur1 != NULL && cur2 != NULL && cur1->value <= cur2->value) {
            curm = cur1;
            cur1 = cur1->next;
            curm->next = NULL;
        }

        // List2: have remaining nodes, List1: not
        else if (cur2 != NULL && cur1 == NULL) {
            curm = cur2;
            cur2 = cur2->next;
            curm->next = NULL;
        }

        // List1: have remaining nodes, List2: not
        else if (cur1 != NULL && cur2 == NULL) {
            curm = cur1;
            cur1 = cur1->next;
            curm->next = NULL;
        }

        // check if mergelist is empty 
        // add current node as first node to it
        if (mergelist == NULL) {
            mergelist = curm;
            prevm = mergelist;
        }
        // add current node to the tail of new merged list
        else {
            prevm->next = curm;
            prevm = prevm->next;
        }
    }

    //Sort list

    return mergelist;
}

Example:

MERGE TEST
List 1: 9 9 5 5 3 3
List 2: 10 10 6 6 1 1
List 1 + 2 Merged:
Merged list: 9 9 5 5 3 3 10 10 6 6 1 1

It is merging the lists side by side and not in ascending order. Any ideas why?
EDIT: I cannot use nested loops. Only one loop may be present.

Answer 1

We beginners should help each other.:)

Take into account that your approach of comparing values of the two lists makes sense only in case when the both lists are sorted in the descending order provided that you want to get a sorted list in the ascending order. Otherwise there is no sense to compare values of two nodes of the lists.

Here you are.

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int value;
    struct node *next;
} Node;

Node * merge( Node *list1, Node *list2 )
{
    Node *mergelist = NULL;

    while ( list1 || list2 )
    {

        _Bool second = ( list1 == NULL ) || 
                       ( list2 != NULL && list1->value < list2->value );

        Node *current;

        if ( second )
        {
            current = list2;
            list2 = list2->next;
        }
        else
        {
            current = list1;
            list1 = list1->next;
        }

        current->next = mergelist;
        mergelist = current;
    }

    return mergelist;
}

void display( Node *list )
{
    for ( ; list; list = list->next )
    {
        printf( "%d ", list->value );
    }
}

void insert_array( Node **list, int a[], size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        Node *current = malloc( sizeof( *current ) );
        current->value = a[i];
        current->next = *list;
        *list = current;
        list = &( *list )->next;
    }
}

int main(void) 
{
    int a[] = { 9, 9, 5, 5, 3, 3 };
    int b[] = { 10, 10, 6, 6, 1, 1 };

    Node *list1 = NULL;
    Node *list2 = NULL;

    insert_array( &list1, a, sizeof( a ) / sizeof( *a ) );
    insert_array( &list2, b, sizeof( b ) / sizeof( *b ) );

    display( list1 );
    putchar( '\n' );

    display( list2 );
    putchar( '\n' );

    Node *mergelist = merge( list1, list2 );

    display( mergelist );
    putchar( '\n' );

    return 0;
}

The program output is

9 9 5 5 3 3 
10 10 6 6 1 1 
1 1 3 3 5 5 6 6 9 9 10 10 

You have to insert each node in the beginning of the merged list.

Also it would be better to declare the function like

Node * merge( Node **list1, Node **list2 );

and inside the function before exit to set *list1 and *list2 to NULL because after executing the function neither list1 nor list2 are valid.

Answer 2

Nevermind. My original code worked fine after tweaking input lists. Thanks everyone. @A1m

/*
Takes two lists and merges them without creating extra nodes. */
Node *merge(Node* list1, Node* list2) {
    Node *mergelist, *cur1, *cur2, *curm, *prevm;
    cur1 = list1, cur2 = list2;
    curm = mergelist;

     cur1 = list1, cur2 = list2;
    mergelist = NULL;

    while (cur1 != NULL || cur2 != NULL) {
        // List2:node < List1:node
        if (cur1 != NULL && cur2 != NULL && cur2->value < cur1->value) {
            curm = cur2;
            cur2 = cur2->next;
            curm->next = NULL;
        }

        // List2:node <= List1:node
        else if (cur1 != NULL && cur2 != NULL && cur1->value <= cur2->value) {
            curm = cur1;
            cur1 = cur1->next;
            curm->next = NULL;
        }

        // List2: have remaining nodes, List1: not
        else if (cur2 != NULL && cur1 == NULL) {
            curm = cur2;
            cur2 = cur2->next;
            curm->next = NULL;
        }

        // List1: have remaining nodes, List2: not
        else if (cur1 != NULL && cur2 == NULL) {
            curm = cur1;
            cur1 = cur1->next;
            curm->next = NULL;
        }

        // check if mergelist is empty 
        // add current node as first node to it
        if (mergelist == NULL) {
            mergelist = curm;
            prevm = mergelist;
        }
        // add current node to the tail of new merged list
        else {
            prevm->next = curm;
            prevm = prevm->next;
        }
    }

    return mergelist;
}

Test Output:

##############
MERGE TEST
List 1: list: 1 1 3 3 5 5 9 9
List 2: list: 2 2 6 6 8 8 8 8
List 1 + 2 Merged:
Merged list: 1 1 2 2 3 3 5 5 6 6 8 8 8 8 9 9
##############
MERGE TEST 2
List 3:list: 1 1 2 2 3 3 5 5 6 6 8 8 8 8 9 9
List 4:list: 1 3 9 12
List 3 + List 4 Merged:
list: 1 1 1 2 2 3 3 3 5 5 6 6 8 8 8 8 9 9 9 12
##############

Answer 3

You can only use your merging algorithm when lists are sorted. This should also be the best option you have, sort then merge. It has better runtimecomplexity than merge then sort. So keep your algorithm but add sorting to it. Pay attention to the correct sort order. (In your example the sort order was flipped).

But aside from that, you shouldn't use the mergeList as you do in the end of your loop. Instead construct the List directly. See the code:

/*
Takes two lists and merges them without creating extra nodes. */
Node *merge(Node* list1, Node* list2) {
    Node *mergelist, *cur1, *cur2, *curm, *prevm;
    cur1 = list1, cur2 = list2;
    curm = mergelist;

    while (cur1 != NULL || cur2 != NULL) {
        if ((cur1 != NULL && cur2 != NULL && cur2->value < cur1->value) || (cur2 != NULL && cur1 == NULL)) {
            curm->next = cur2;
            curm = curm->next;
            cur2 = cur2->next;

        } else if ((cur1 != NULL && cur2 != NULL && cur1->value <= cur2->value) || (cur1 != NULL && cur2 == NULL)) {
            curm->next = cur1;
            curm = curm->next;
            cur1 = cur1->next;
        }
    }
    return mergelist->next;
}