/**
	 * Returns the sum of two polynomials - DOES NOT change either of the input polynomials.
	 * The returned polynomial MUST have all new nodes. In other words, none of the nodes
	 * of the input polynomials can be in the result.
	 *
	 * @param poly1 First input polynomial (front of polynomial linked list)
	 * @param poly2 Second input polynomial (front of polynomial linked list
	 * @return A new polynomial which is the sum of the input polynomials - the returned node
	 *         is the front of the result polynomial
	 */
	public static Node add(Node poly1, Node poly2) {
		if (poly1 == null && poly2 == null) return null;
		if (poly1 == null) return poly2;
		if (poly2 == null) return poly1;
		Node front = new Node(0, 0, null);
		Node ptr = front;
		while (poly1 != null && poly2 != null) {
			if (poly1.term.degree == poly2.term.degree) {
				ptr.term.degree = poly1.term.degree;
				ptr.term.coeff = poly1.term.coeff + poly2.term.coeff;
				poly1 = poly1.next;
				poly2 = poly2.next;
			} else if (poly1.term.degree < poly2.term.degree) {
				ptr.term.degree = poly1.term.degree;
				ptr.term.coeff = poly1.term.coeff;
				poly1 = poly1.next;
			} else if (poly1.term.degree > poly2.term.degree) {
				ptr.term.degree = poly2.term.degree;
				ptr.term.coeff = poly2.term.coeff;
				poly2 = poly2.next;
			}
			ptr.next = new Node(0, 0, null);
			ptr = ptr.next;
		}

		Node ptr2 = null;
		if (poly1 != null) ptr2 = poly1;
		if (poly2 != null) ptr2 = poly2;
		while (ptr2 != null) {
			ptr.term.degree = ptr2.term.degree;
			ptr.term.coeff = ptr2.term.coeff;
			if (ptr2.next != null) {
				ptr.next = new Node(0, 0, null);
				ptr = ptr.next;
			}
			ptr2 = ptr2.next;
		}
		simplify(front);
		return front;
	}

	private static void simplify(Node first) {
		Node ptr1 = first;
		Node ptr2;
		Node tmp;

		while (ptr1 != null && ptr1.next != null) {
			ptr2 = ptr1;

			while (ptr2.next != null) {
				if (ptr1.term.degree == ptr2.next.term.degree) {
					ptr1.term.coeff = ptr1.term.coeff + ptr2.next.term.coeff;
					tmp = ptr2.next;
					ptr2.next = ptr2.next.next;
				} else {
					ptr2 = ptr2.next;
				}
			}
			ptr1 = ptr1.next;
		}
	}