🚀 go-pugleaf

The algorithm you want to use is the list merge algorithm.  Here's the
pseudo-code:

list * p1 = head_of_p1;
list * p2 = head_of_p2;
list * pOut = NULL;

sort_list_ascending_by_exponent (p1);
sort_list_ascending_by_exponent (p2);

while (p1 != NULL || p2 != NULL)
{
	if (p2 == NULL || p1->exponent < p2->exponent)
	{
		add_to_list (pOut, copy_of (p1));
		p1 = p1 -> next;
	}
	else
	if (p1 == NULL || p2->exponent < p1->exponent)
	{
		add_to_list (pOut, copy_of (p2));
		p2 = p2 -> next;
	}
	else
	if (p1->coefficent + p2->coefficent != 0)
	{
		list * p = new list;
		p->exponent = p1->exponent;
		p->coefficent = p1->coefficent + p2->coefficent;
		add_to_list (pOut, p);
		p1 = p1 -> next;
		p2 = p2 -> next;
	}
}

Your exercise is to generalize the algorithm for n lists. :->

Sincerely,
Will McKee.

-- 
---------------------------------------
William A. McKee
wamckee@cjkware.com
http://www.cjkware.com


Brian McSweeney <mcsweenb@tcd.ie> wrote in article
<34FC5E36.252831A1@tcd.ie>...
> Poor student studying for a scholarship exam in a week!!
> 
> I want to know how (as simply as possible) to insert objects into a
> linked list.
> 
> Example question:
> 
> "Define a linked list that can represent a polynomial.  Then write  a
> method to add on another polynomial (ie link them) to the current one,
> and a method to add the one polynomial to another."
> 
> Now I know how to define the linked list - a class that has an exponent
> and a coefficient and a pointer to objects of that class, and I know how
> to create the list.  I also know that to add on another linked list to
> the current one you just traverse the first list and then set its end
> pointer to the pointer to the start of the second list.
>      But how do you do the add method?  the exponent term of one may be
> different to that of the other and in that case it will have to be
> inserted somehow??
> eg. (3x^2 +2x^5) + (2x + x^3+x^5) = 2x+3x^2+x^3+3x^5
> 
> I am so grateful to you if you can reply to me at
> "mcsweeenb@tcd.ie"
>