So I was trying to merge two linked lists but I am getting a segmentation fault
The two linked lists were (1)->(2)->(3) and (1)->(3)->(4). The output remains the same even when I malloc l and k. The program works fine till the merge function is called. A little detailed explanation will help a lot as I am a beginner.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int val;
struct node *next;
} node;
typedef struct linkedlist
{
node *head;
node *tail;
} linkedlist;
void createlinkedlist(linkedlist *l)
{
l->head = NULL;
l->tail = NULL;
}
void push(linkedlist *l, int value)
{
node *newnode = (node *)malloc(sizeof(node));
if (newnode == NULL)
{
printf("insertion failed");
return;
}
newnode->val = value;
newnode->next = NULL;
if (l->tail != NULL)
{
l->tail->next = newnode;
}
l->tail = newnode;
if (l->head == NULL)
{
l->head = newnode;
}
}
void display(linkedlist *l)
{
node *printval = l->head;
printf("\n");
while (printval != NULL)
{
printf("%d-->", printval->val);
printval = printval->next;
}
}
void merge(linkedlist *l, linkedlist *k)
{
node *lnext = l->head->next;
node *lprevious = l->head;
node *rprevious = k->head;
node *rnext = k->head->next;
if ((lprevious->val) <= (rprevious->val))
{
node *h = lprevious;
while (lprevious != NULL && rprevious != NULL)
{
if (lprevious->val <= rprevious->val)
{
lprevious->next = rprevious;
rprevious->next = lnext;
rprevious = rnext;
rnext = rnext->next;
lprevious = lprevious->next;
}
else
{
lprevious = lprevious->next;
lnext = lnext->next;
}
}
l->head = h;
}
else
{
// node *h = head2;
// while (previous != NULL || head2 != NULL) {
}
}
int main()
{
linkedlist l;
linkedlist k;
createlinkedlist(&l);
createlinkedlist(&k);
push(&l, 1);
push(&l, 2);
push(&l, 4);
push(&k, 1);
push(&k, 3);
push(&k, 4);
display(&k);
display(&l);
merge(&l, &k);
display(&l);
}
The output which I am getting.
1-->3-->4-->
Segmentation fault (core dumped)
And the worst part is my debugger is not showing any faults.
It seems you are trying to merge lists in the ascending order.
Your function merge has several bugs.
The first one is that it does not take into account that in general one or both lists passed to the function can be empty. In this case these statements in the beginning of the function
node *lnext = l->head->next;
node *rnext = k->head->next;
already invoke undefined behavior.
The same problem exists within the while loop in these statements
rnext = rnext->next;
lnext = lnext->next;
because pointers rnext and lnext can be null pointers.
Also there are logical errors in the if statement within the while loop.
At least if lprevious->val is not greater than rprevious->val it does not mean that you need to insert the node rprevious after the node lprevious.
if (lprevious->val <= rprevious->val)
{
lprevious->next = rprevious;
rprevious->next = lnext;
rprevious = rnext;
rnext = rnext->next;
lprevious = lprevious->next;
}
else
{
lprevious = lprevious->next;
lnext = lnext->next;
}
On the other hand, if lprevious->val is greater than rprevious->val then it does not mean that you have to move to the second node lprevious->next.
And the function does not take into account the pointers l->tail and r->tail that it shall to change.
The function code will be more clear if at first just to form a new list based on the given two lists and then to set the first list to the formed list and to make the second list as an empty list.
Bear in mind that you need to write also a function that will free all the allocated memory for nodes of lists.
Also the parameter of the function display should have qualifier const
void display( const linkedlist *l)
because the function does not change passed lists.
And the function push should not display any message.
if (newnode == NULL)
{
printf("insertion failed");
return;
}
It is the caller of the function will decide whether to output a message. And moreover the caller of the function should have a possibility to know the result of a function call. That is the function should report to the caller a failure or a success through its return value.
Here is a demonstration program that shows how the function merge can be implemented.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int val;
struct node *next;
} node;
typedef struct linkedlist
{
node *head;
node *tail;
} linkedlist;
int push( linkedlist *l, int value )
{
node *newnode = malloc( sizeof( node ) );
int success = newnode != NULL;
if (success)
{
newnode->val = value;
newnode->next = NULL;
if (l->head == NULL)
{
l->head = newnode;
}
else
{
l->tail->next = newnode;
}
l->tail = newnode;
}
return success;
}
void merge( linkedlist *l, linkedlist *r )
{
node *head = NULL;
node *tail = NULL;
node **current = &head;
while (l->head != NULL && r->head != NULL)
{
if (r->head->val < l->head->val)
{
*current = r->head;
r->head = r->head->next;
}
else
{
*current = l->head;
l->head = l->head->next;
}
tail = *current;
current = &( *current )->next;
}
if (l->head != NULL)
{
*current = l->head;
tail = l->tail;
}
if ( r->head != NULL )
{
*current = r->head;
tail = r->tail;
}
l->head = head;
l->tail = tail;
r->head = r->tail = NULL;
}
FILE *display( const linkedlist *l, FILE *fp )
{
for (const node *current = l->head; current != NULL; current = current->next)
{
fprintf( fp, "%d -> ", current->val );
}
fputs( "null", fp );
return fp;
}
void clear( linkedlist *l )
{
while (l->head)
{
node *current = l->head;
l->head = l->head->next;
free( current );
}
l->tail = l->head;
}
int main( void )
{
linkedlist l = { .head = NULL, .tail = NULL };
for (int i = 0; i < 10; i += 2)
{
push( &l, i );
}
fputc( '\n', display( &l, stdout ) );
linkedlist r = { .head = NULL, .tail = NULL };
for (int i = 1; i < 10; i += 2)
{
push( &r, i );
}
fputc( '\n', display( &r, stdout ) );
putchar( '\n' );
merge( &l, &r );
fputc( '\n', display( &l, stdout ) );
fputc( '\n', display( &r, stdout ) );
clear( &l );
}
The program output is
0 -> 2 -> 4 -> 6 -> 8 -> null
1 -> 3 -> 5 -> 7 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
null
And at last one more important remark. If you want to build sorted lists then the function push should be rewritten to provide inserting new nodes in the ascending order.
In this case the function can look the following way
int push( linkedlist *l, int value )
{
node *newnode = ( node * )malloc( sizeof( node ) );
int success = newnode != NULL;
if (success)
{
newnode->val = value;
node **current = &l->head;
while (*current != NULL && !( newnode->val < ( *current )->val ))
{
current = &( *current )->next;
}
newnode->next = *current;
*current = newnode;
if ( newnode->next == NULL )
{
l->tail = newnode;
}
}
return success;
}