here is a recursive method. First sort the two list and use the following
algo.
initial value of third parameter is NULL.
struct node *sortedIntersect(struct node *a, struct node *b,
struct node *result)
{
/* base case */
if(a == NULL || b == NULL)
{
return NULL;
}
/* If both lists are non-empty */
/* advance the smaller list and call recursively */
if(a->data < b->data)
{
return sortedIntersect(a->next, b, result);
}
else if(a->data > b->data)
{
return sortedIntersect(a, b->next, result);
}
else if(a->data == b->data)
{
/* If same data is found then allocate memory */
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = a->data;
/* If the first node is being added to resultant list */
if(result == NULL)
{
result = temp;
}
/* Else change the next of result and move result to next */
else
{
result->next = temp;
result = temp;
}
/* advance both lists and call recursively */
result->next = sortedIntersect(a->next, b->next, result);
}
return result;
On Wednesday, 4 July 2012 22:41:57 UTC+5:30, Abhi wrote:
>
> Any efficient algorithm to find intersection of two linked lists.Example:
> Linked List 1) 1 -> 2 -> 3 -> 4 -> 5 -> 6
> Linked List 2) 3 -> 4 -> 5
>
> Intersection 4 -> 5 -> 6
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/i7XgIpbhWhIJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
