Creating a Linked List of common elements from two other linked lists..

[jjroyale]

Hello all,

I'm trying to write a function that takes two linked lists and creates a third one with only the common elements.

It assumes the first list (the caller) has no dups, but it doesn't seem to be working. The program doesn't crash, it just hangs when it is supposed to display L3 (the third list)..everything else runs and is displayed fine.

Thanks in advance.

template <typename T>
LList <T> LList <T>:: common (LList <T> &B)	//common fct
{
	Node <T> *hunter1 = Head;
	Node <T> *hunter2 = B.Head;
	Node <T> *newTerm;
	int flag = 0;
	LList C;
	
	while (hunter1->link != NULL)	//put all of list 1 into new list
	{
			newTerm = new Node <T>;
			newTerm->link = NULL;
			newTerm->data = hunter1->data;
			C.append(newTerm);
			hunter1 = hunter1->link;
	}
	
	while (hunter2->link != NULL)	//traverse through 2nd list
	{
		hunter1 = Head;	//reset hunter1 to Head of List 1 
		flag = 0;	//assume we do not have a dup
		while (hunter1->link != NULL)	//traverse through 1st list
		{
			if (hunter2->data == hunter1->data)	//if the item we are looking at in 2nd list
												//is anywhere in the 1st
			{
				flag = 1;	//raise the flag
			}
		}
		if (flag == 0)	//if flag was not raised
		{
			newTerm = new Node <T>;	//get memory allocation for a newTerm
			newTerm->data = hunter2->data; //put this data in it
			newTerm->link = NULL;	//mark the end null
			C.append (newTerm);	//add it to our new list
		}
		hunter2 = hunter2->link;	//move hunter down
	}
	return C;
}

Main fct:

int main()
{
	LList <int> L1, L2, L3;	//Declaring a Linked List
	
	cout << "You will create two linked lists.\nA third one will be created with only common elements\n\n\n";
	
	L1.create();
	cout << "\nList 1: ";
	L1.display();
	
	L2.create();
	cout << "\nList 2: ";
	L2.display();
	
	L3 = L1.common(L2);
	cout << "\nCommon List: ";
	L3.display();
	
	
	return 0;
}

[MiiNiPaa]

http://en.cppreference.com/w/cpp/algorithm/set_intersection
You should make sure that your list can provide valid InputIterators though.
Also you can look into implementation and make something similar.

[jjroyale]

I honestly think my algorithm should work.. I just tried another program using a similar function and my program is hanging again..something is causing it to hang..

[jjroyale]

Heres an example of a function that should delete a node after a negative number..

template <typename T>
void LList <T> :: afterNegative ()	//deletes node after a negative number
{
	Node <T> *hunter = Head, *temp;
	
	if (hunter->data < 0)
	{
		Head = Head->link;
		delete hunter;
	}
	else
	{
		while (hunter->link != NULL)	
		{
			if (hunter->link->data < 0)
			{
				temp = hunter->link;
				hunter->link = temp->link;
				temp->link = NULL;
				delete temp;
			}
		}
	}
}

same problem..it just hangs

[Peter87]

In the loop conditions you should check if hunterX is null instead of hunterX->link.

[MikeyBoy]

Have you tried running it in a debugger, so that you can step through it and see what it's doing?

If it's hanging, it's probably because one of your while loops is looping infinitely.

[jjroyale]

Looking at the original problem when I change line 10
while (hunter1->link != NULL) //put all of list 1 into new list

to

while (hunter1 != NULL) //put all of list 1 into new list

now it prints out random numbers infinitely, looks like addresses...

[MikeyBoy]

Have you tried running it in a debugger, so that you can step through it and see what it's doing?

[jjroyale]

Not much experience using the debugger in Dev..

[jjroyale]

Figured it out, in the while loop I wasn't moving hunter along..

[jjroyale]

However, still cant get my original question to work..