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
```

answered on Stack Overflow Dec 14, 2019 by Vlad from Moscow • edited Dec 14, 2019 by Jonathan Leffler

User contributions licensed under CC BY-SA 3.0