merge two sorted linked list into one linked list (recursion)

I had to write a recursive function that receives two sorted lists:

typedef struct listNode {
    int* dataPtr;
    struct listNode* next;
} ListNode;

typedef struct list
{
    ListNode* head;
    ListNode* tail;
} List;

and merge them into one sorted list.

I wrote these functions:

void mergeRec(ListNode* head1, ListNode* head2, ListNode* mergedList)
{
    if (head1 == NULL && head2 == NULL)
        return;
    else if (head1 == NULL) {
        mergedList->next = head2;
        head2 = head2->next;
    }
    else if (head2 == NULL) {
        mergedList->next = head1;
        head1 = head1->next;
    }
    else if (*(head1->dataPtr) > *(head2->dataPtr)) {
        mergedList->next = head1;
        head1 = head1->next;
    }
    else
    {
        mergedList->next = head2;
        head2 = head2->next;
    }

    mergeRec(head1, head2, mergedList->next);
}

List merge(List lst1, List lst2)
{
    List mergedList;
    makeEmptyList(&mergedList);
    mergeRec(lst1.head, lst2.head, mergedList.head);
    return mergedList;
}

Now, the problem I have with the recursive function is that at the first call when merged list is pointing to null, so obviously when I write something like mergeList->next I will get a running bug.

I tried to solve it by adding the following condition in the recursion:

    if (mergedList == NULL)
    {
        if (*(head1->dataPtr) > *(head2->dataPtr))
        {
            mergedList = head1;
            head1 = head1->next;
        }
        else
        {
            mergedList = head2;
            head2 = head2->next;
        }
    }

but I got this error:

"Exception thrown at 0x00661EB9 in q2d.exe: 0xC0000005: Access violation writing location 0x01000F48."

I can't tell the problem, or how do I solve it. I would very much appreciate your help.

Thanks!

For starters it is entirely unclear why in this structure there is a data member of type int *

typedef struct listNode {
    int* dataPtr;
    struct listNode* next;
}List;

instead of just of type int

typedef struct listNode {
    int data;
    struct listNode* next;
}List;

Nevertheless, the functions merge and mergeRec are invalid because they deal with copies of values of lists and of pointers list1.head, list2.head, and mergedList.head.

List merge(List lst1, List lst2)
mergeRec(lst1.head, lst2.head, mergedList.head);

Moreover the pointers list1.tail, list2.tail, and mergedList.tail are ignored.

I can suggest the following solution shown in the demonstrative program below.

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

typedef struct listNode 
{
    int *dataPtr;
    struct listNode *next;
} ListNode;

typedef struct list
{
    ListNode *head;
    ListNode *tail;
} List;

void makeEmpty( List *list )
{
    list->head = list->tail = NULL;
}

int push( List *list, int data )
{
    ListNode *current = malloc( sizeof( ListNode ) );
    int success = current != NULL;

    if ( success )
    {
        current->dataPtr = malloc( sizeof( int ) );
        success = current->dataPtr != NULL;

        if ( success )
        {
            *current->dataPtr = data;
            current->next = NULL;

            if ( list->head == NULL )
            {
                list->head = list->tail = current;
            }
            else
            {
                list->tail = list->tail->next = current;
            }
        }
        else
        {
            free( current );
            current = NULL;
        }
    }

    return success;
}

List merge( List *first, List *second )
{
    List result;
    makeEmpty( &result );

    if ( ( second->head != NULL ) && 
         ( first->head == NULL || *second->head->dataPtr < *first->head->dataPtr ) )
    {
        result.head = result.tail = second->head;
        second->head = second->head->next;
        if ( second->head == NULL ) second->tail = NULL;
    }
    else if ( first->head != NULL )
    {
        result.head = result.tail = first->head;
        first->head = first->head->next;
        if ( first->head == NULL ) first->tail = NULL;
    }

    if ( !( first->head == NULL && second->head == NULL ) )
    {
        List tmp = merge( first, second );
        result.head->next = tmp.head;
        result.tail = tmp.tail;
    }

    return result;
}

void output( const List *list )
{
    for ( const ListNode *current = list->head; current != NULL; current = current->next )
    {
        printf( "%d ", *current->dataPtr );
    }

    puts( "NULL" );
}

int main(void) 
{
    List even_numbers;
    List odd_numbers;

    makeEmpty( &even_numbers );
    makeEmpty( &odd_numbers );

    const int N = 10;

    for ( int i = 0; i < N; i++ ) 
    {
        i % 2 == 0 ? push( &even_numbers, i )
                   : push( &odd_numbers, i );
    }

    printf( "even_numbers: " ); output( &even_numbers );
    printf( "odd_numbers:  " ); output( &odd_numbers );

    List all_numbers = merge( &even_numbers, &odd_numbers );

    printf( "all_numbers:  " ); output( &all_numbers );
    printf( "even_numbers: " ); output( &even_numbers );
    printf( "odd_numbers:  " ); output( &odd_numbers );

    return 0;
}

The program output is

even_numbers: 0 2 4 6 8 NULL
odd_numbers:  1 3 5 7 9 NULL
all_numbers:  0 1 2 3 4 5 6 7 8 9 NULL
even_numbers: NULL
odd_numbers:  NULL