Intersection of two unsorted Linked LIst

[CSharpque]

Anyone can tell me logic for two unsorted linked list. I have create two linked list named First and second . Now how to generate intersection linked list named third?

[hamsterman]

Take an element from first, then search for it in second. If it's there, add it to third. That'll be two for loops. Although you could use std::find, you probably shouldn't.

[ne555]

Sort the list, and apply the 'intersection of sorted list' algorithm. (its order will be better)

[JLBorges]

If a bit of extra memory is (temporarily) available:

template< typename T > // T is LessThanComparable
std::list<T> intersection( const std::list<T>& a, const std::list<T>& b )
{
   std::vector< std::reference_wrapper<const T> > aa( a.begin(), a.end() ) ;
   std::vector< std::reference_wrapper<const T> > bb( b.begin(), b.end() ) ;
   
   std::sort( aa.begin(), aa.end() ) ;
   std::sort( bb.begin(), bb.end() ) ;

   std::list<T> result ;
   std::set_intersection( aa.begin(), aa.end(), bb.begin(), bb.end(),
                          std::back_inserter(result) ) ;
   return result ;
}

[GFreak45]

or you could have another member storing the "base" node of each list, which points to the other base nodes... ie:

class list
{
public:
    list ()
    {
        this->nextList = &base;
        this->prevList = base.prevList;
        this->prevList->nextList = this;
        this->nextList->prevList = this;
        this->next = this;
        this->prev = this;
        this->list = this;
    }
    
    list (list* list)
    {
        this->list = list->list;
        this->next = this->list;
        this->prev = this->list->prev;
        this->next->prev = this;
        this->prev->next = this;
        this->nextList = this->list->nextList;
        this->prevList = this->list->prevList;
    }
    
    list *next,
        *prev,
        *list,
        *nextList,
        *prevList;
} base;

i probably have some errors in there cuz this is texted but i think u gmight get the idea from that...

[CSharpque]

if i take first element of first list and compre it with each elements of second list then code for it

first_current=first;
	second_current=second;

	while(first_current->next!=NULL)
	{
		while(second_current->next!=NULL)
		{
			if(first_current->data== second_current->data)
			{
				if (third==NULL)
				{
					temp=(struct list*)malloc(sizeof(struct list));
					temp->data=first->data;
					temp->next=NULL;
					third=temp;
					third_current=third;

				}
				else
				{
					temp=(struct list*)malloc(sizeof(struct list));
					temp->data=first->data;
					temp->next=NULL;
					third_current->next=temp;
					third_current=third_current->next;

				}
				second_current=second_current->next;
			}
		        second_current=second_current->next;
		}
	}
	display(third);

but program goes infinite....

[hamsterman]

You never advance first_current.

[CSharpque]

can you elaborate what are you saying?

[ne555]

while(first_current->next!=NULL) ¿how are you expecting to break the loop? You never change first_current to traverse the list.

[CSharpque]

first_current=first;
	second_current=second;

	while(first_current->next!=NULL)
	{
		while(second_current->next!=NULL)
		{
			if(first_current->data== second_current->data)
			 {
				if (third==NULL)
				{
					temp=(struct list*)malloc(sizeof(struct list));
					temp->data=first->data;
					temp->next=NULL;
					third=temp;
					third_current=third;
					

				}
				else
				{
					temp=(struct list*)malloc(sizeof(struct list));
					temp->data=first->data;
					temp->next=NULL;
					third_current->next=temp;
					third_current=third_current->next;
					

				}
				first_current=first_current->next;
			}
			else
				second_current=second_current->next;
		}
	}
	display(third)

now i have changed but still program go infinite

[CSharpque]

or you can suggest me any other simple logic...but on unsorted linked list.

[CSharpque]

i have modify that program now program work properly but one problem is there last element can take if it is same in both list i know reason but what to do i don't know...reason is that when current pointer( of any list whether it is of first or second )reach at last node at that time while condition become true and last node data can 't compare so it will be not added in to third list. The code for that is

first_current=first;
	second_current=second;
	
	while(first_current->next!=NULL)
	{
		while(second_current->next!=NULL)
		{
			if(first_current->data== second_current->data)
			 {
				
				if (third==NULL)
				{
					temp=(struct list*)malloc(sizeof(struct list));
					temp->data=first->data;
					temp->next=NULL;
					third=temp;
					third_current=third;



				}
				else
				{
					temp=(struct list*)malloc(sizeof(struct list));
					temp->data=first->data;
					temp->next=NULL;
					third_current->next=temp;
					third_current=third_current->next;


				}
				second_current=second_current->next;

				//first_current=first_current->next;
			}
			else
				second_current=second_current->next;


		}
                second_current=second;
		first_current=first_current->next;
	}
	display(third);

[hamsterman]

Remove ->next from the while conditions. It only needs to be _current != NULL.

[CSharpque]

still it does not give intersection in all the possible input....
and is there any difference between current->next!=NULL and current!=NULL
I think both are same...Is it right?

[CSharpque]

k i got may mistake . inside second while loop, the variable is temp->data=first_current->data instead temp->data=first->data same changes in else part of IF condition...
But can you tell me difference between current!=NULL and current->next!=NULL?

[CSharpque]

k i got that difference that is current means address of that node and current->next store the address of next node...
thanks for proper suggestion