I am working on a problem that gives two sorted linked lists and asks to find the intersection of two lists and create a new list with the elements as the common elements.
I am attaching my code.
#include<stdio.h>
#include<stdlib.h>
struct node{
int val;
struct node *next;
};
void getval(struct node *p)
{
scanf("%d",&p->val);
p->next=NULL;
}
void createlist(struct node **p , int n)
{
int i=0;
struct node *str =NULL;
for( i=0;i<n;i++)
{
if(*p==NULL)
{
*p = (struct node*)malloc(sizeof(struct node));
str = (struct node*)malloc(sizeof(struct node));
*p = str;
getval(*p);
}
else
{
str->next = (struct node*)malloc(sizeof(struct node));
getval(str->next);
str=str->next;
}
if(i==n-1)
{
str=NULL;
}
}
}
void intersectlist(struct node *p1 , struct node *p2 )
{
int i=0,j=0;
struct node *head3=NULL;
struct node *str= NULL;
struct node *p3= NULL;
for(i=0;p1!=NULL;i++)
{
p3=p2;
for(j=0;p3!=NULL;j++)
{
if(p1->val == p3->val)
{
if(head3==NULL)
{
head3 = (struct node*)malloc(sizeof(struct node));
str = (struct node*)malloc(sizeof(struct node));
head3 = str;
head3->val=p3->val;
}
else
{
str->next = (struct node*)malloc(sizeof(struct node));
str->val = p3->val;
str=str->next;
}
break;
}
p3=p3->next;
}
p1= p1->next;
}
str = NULL;
struct node *p = NULL;
p=head3;
while(p!=NULL)
{
printf("%d ",p->val);
p=p->next;
}
}
int main(){
struct node *head1=NULL;
struct node *head2=NULL;
int i,a=0,n1=0,n2=0;
printf("enter the size of list 1 :");
scanf("%d",&n1);
printf("enter the elements of list 1 :");
createlist(&head1,n1);
printf("enter the size of list 2 :");
scanf("%d",&n2);
printf("enter the elements of list 2 : ");
createlist(&head2,n2);
intersectlist(head1 , head2);
return 0;
}
Here in the function intersectlist, even though p1( which is head1) is not null, the function doesn't enter the loop. It simply exits the loop and jumps directly to the line (str=NULL). Why is this happening
Here in the function intersectlist, even though p1( which is head1) is not null, the function doesn't enter the loop.
That is no true. I compiled and ran your program and both loops where entered.
Yet, the result is wrong.
The problem is your code to copy the found duplicates into the new list:
if(head3==NULL)
{
head3 = (struct node*)malloc(sizeof(struct node));
str = (struct node*)malloc(sizeof(struct node));
head3 = str;
head3->val=p3->val;
}
else
{
str->next = (struct node*)malloc(sizeof(struct node));
str->val = p3->val;
str=str->next;
}
Here, first of all in the if branch you create a memory leak by allocating memory for head3. 2 lines later you overwrite that address by another value and you can never free that first one. The same error exists in your function to create the lists.
Then your main error happens in the else part:
You overwrite the value from first node with value from the new node. Remember: str still holds the address of head3 when you come here for the first time. You must advance the pointer first and afterwards assign content.
Then, you have another problem as you do not terminate your new list.
You seem to intent to do it with str = NULL; after your loops but that does not help. You only assign to str, not to str->next.
Besides that, you have ununsed variables in main. Also the loop variables i and j are completely useless. You only use pointers in your loop, no need to mess with additional counters.
Your loops could look like this to do the very same:
for( ; p1 != NULL; )
{
p3=p2;
for( ; p3 != NULL; )
And if you don't have initialization and end-of-loop operation, then you could just use while loops instead.
All in all a fixed version looks like this:
#include<stdio.h>
#include<stdlib.h>
struct node{
int val;
struct node *next;
};
void getval(struct node *p)
{
scanf("%d",&p->val);
p->next=NULL;
}
void createlist(struct node **p , int n)
{
int i=0;
struct node *str =NULL;
for (i=0;i<n;i++)
{
if (*p==NULL)
{
str = malloc(sizeof(struct node));
*p = str;
getval(*p);
}
else
{
str->next = malloc(sizeof(struct node));
getval(str->next);
str=str->next;
}
if (i==n-1)
{
str=NULL;
}
}
}
void intersectlist(struct node *p1 , struct node *p2 )
{
struct node *head3=NULL;
struct node *str= NULL;
struct node *p3= NULL;
whlie (p1 != NULL)
{
p3=p2;
while (p3 != NULL)
{
if (p1->val == p3->val)
{
if (head3==NULL)
{
str = malloc(sizeof(struct node));
head3 = str;
head3->val=p3->val;
}
else
{
str->next = malloc(sizeof(struct node));
str=str->next;
str->val = p3->val;
str->next = NULL;
}
break;
}
p3=p3->next;
}
p1= p1->next;
}
struct node *p = head3;
while (p!=NULL)
{
printf("%d ",p->val);
p=p->next;
}
printf("\n");
}
int main(void)
{
struct node *head1=NULL;
struct node *head2=NULL;
int n1=0,n2=0;
printf("enter the size of list 1 :");
scanf("%d",&n1);
printf("enter the elements of list 1 :");
createlist(&head1,n1);
printf("enter the size of list 2 :");
scanf("%d",&n2);
printf("enter the elements of list 2 : ");
createlist(&head2,n2);
intersectlist(head1 , head2);
return 0;
}
output:
enter the size of list 1 :3
enter the elements of list 1 :2 3 4
enter the size of list 2 :4
enter the elements of list 2 : 2 4 6 7
2 4
Additional hints:
Both lists are sorted. Therefore you wouldn't need to start the inner loop from head of second list each time. Instead you might just continue where you left the inner loop last time.
Mixing list management (p->next=NULL;) with entering payload isn't really straight forward. Instead you should put that line to where you allocate and link the nodes for your list. Otherwise it will confuse readers. Remember: A while after writing some code you will also just be a reader of that code and will get confused as well.
Also, in C you do not need to cast return value of malloc and you should not do it. A cast might hide errors that the compiler could detect otherwise.