Intersection of two Sorted Linked Lists

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

typedef struct Node{
int data;
struct Node *next;
}Node;

typedef Node *list;


list intersect(list l1, list l2)
{
if(!l1 || !l2) return NULL;

if(l1->data == l2->data)
{
l1->next = intersect(l1->next, l2->next);
return l1;
}
else if(l1->data < l2->data)
{
return intersect(l1->next, l2);
}

return intersect(l1, l2->next);
}


list sortedinsert(list l, int n)
{
Node * node = calloc(1, sizeof(Node));
node->data = n;

if(!l)
return node;

Node *p;

for(p = l; p->next && p->next->data < n; p = p->next);

node->next = p->next;

p->next = node;

return l;
}

void printlist(list l1)
{
Node *p;

for(p = l1; p ; p = p->next)
printf("%d->",p->data);

printf("\n");
}

int main()
{
list l1 = NULL, l2 = NULL;

int m, n, i;

scanf("%d", &n);

for(i = 0; i < n; ++i)
{
scanf("%d", &m);
l1 = sortedinsert(l1, m);
}

printlist(l1);

scanf("%d", &n);
for(i = 0; i < n; ++i)
{
scanf("%d", &m);
l2 = sortedinsert(l2, m);
}
printlist(l2);

l1 = intersect(l1, l2);
printlist(l1);

return 0;
}


Advertisements

3 thoughts on “Intersection of two Sorted Linked Lists

  1. A small correction is required in function "intersect".————————————————-if(l1->data = l2->data){ l1->next = intersect(l1->next, l2->next); return l1;}————————————————-if(l1->data == l2->data){ l1->next = intersect(l1->next, l2->next); return l1;}

  2. i could n't understand how the pointer returned by intersect() function is being used to create a new intersection list since it is being called recursively …kindly explain

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s