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

0

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!

c
recursion
linked-list
asked on Stack Overflow Dec 13, 2019 by sharon • edited Dec 14, 2019 by Steve Friedl

## 1 Answer

0

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