Add Two Polynomials Represented as Linked Lists

Problem Statement

A polynomial linked list is an innovative way of using linked lists, where every node encapsulates a single term of a polynomial. The nodes consist of three parts:

• coefficient: This is an integral value representing the number multiplier for the respective term of the polynomial. For instance, in the term 9x^4, the coefficient would be 9.
• power: This represents the exponent part of the term, indicating the degree of the term. For the term 9x^4, the power is 4.
• next: A pointer that leads to the next node or null if it is the end of the list.

Each linked list maintains its terms in a strictly decreasing order according to the power values, ensuring a standardized representation of the polynomial. Coefficients of zero are intentionally omitted to keep the representation succinct.

Given the heads of two polynomial linked lists, our goal is to provide a new linked list representing the sum of these two polynomials. The data structure handling the polynomial terms is denoted as [coefficient, power], and examples might be detailed as [[5,3],[4,1],[-7,0]] to represent a polynomial such as 5x^3 + 4x - 7.

Examples

Example 1

Input:

poly1 = [[1,1]], poly2 = [[1,0]]

Output:

[[1,1],[1,0]]

Explanation:

poly1 = x. poly2 = 1. The sum is x + 1.

Example 2

Input:

poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]

Output:

[[5,2],[2,0]]

Explanation:

poly1 = 2x2 + 4x + 3. poly2 = 3x2 - 4x - 1. The sum is 5x2 + 2. Notice that we omit the "0x" term.

Example 3

Input:

poly1 = [[1,2]], poly2 = [[-1,2]]

Output:

[]

Explanation:

The sum is 0. We return an empty list.

Constraints

• 0 <= n <= 104
• -109 <= PolyNode.coefficient <= 109
• PolyNode.coefficient != 0
• 0 <= PolyNode.power <= 109
• PolyNode.power > PolyNode.next.power

Approach and Intuition

While combining two polynomials using their linked list representations, the method can be visualized like manually adding polynomials:

1. Initiate a pointer for each linked list (poly1 and poly2).

2. Compare the power of the current nodes of both lists:

   • If poly1.power is greater than poly2.power, append poly1's term to the result and move its pointer forward.
   • If poly2.power is greater than poly1.power, append poly2's term and advance its pointer.
   • If their powers are equal, add their coefficients. If the result is non-zero, append it to the result list, then move both pointers forward.

3. Continue this process until you have processed all elements from both lists.

4. Any leftover terms from either list (if lists are of unequal length or one list finishes first) should be directly appended to the result (since other terms not countered in the sum are already in the sorted order).

Example Based Insights:

• Example 1: Merging [[1,1]] and [[1,0]], straightforwardly gives [[1,1],[1,0]] since the terms' powers differ, and they are appended as they are.

• Example 2: This example illustrates non-zero coefficient aggregation where similar powers exist. 2x^2 + 4x + 3 and 3x^2 - 4x - 1 result in default aggregative behaviors, giving [[5,2],[2,0]], where middle terms with the same power cancel each other out.

• Example 3: Shows the scenario of a perfect cancellation, where [[1,2]] and [[-1,2]] sum up to an empty list due to zero coefficient for the only existing power.

Solutions

class Solution {
public:
    PolyNode* mergePolynomials(PolyNode* poly1, PolyNode* poly2) {
        PolyNode* head1 = poly1;
        PolyNode* head2 = poly2;
    
        PolyNode* dummy = new PolyNode();
        PolyNode* tail = dummy;
    
        while (head1 != NULL && head2 != NULL) {
            if (head1->power == head2->power) {
                if (head1->coefficient + head2->coefficient != 0) {
                    tail->next = new PolyNode(head1->coefficient + head2->coefficient, head1->power);
                    tail = tail->next;
                }
                head1 = head1->next;
                head2 = head2->next;
            } else if (head1->power > head2->power) {
                tail->next = head1;
                head1 = head1->next;
                tail = tail->next;
            } else {
                tail->next = head2;
                head2 = head2->next;
                tail = tail->next;
            }
        }
            
        if (head1 == NULL) {
            tail->next = head2;
        } else {
            tail->next = head1;
        }
        return dummy->next;
    }
};