1634. Add Two Polynomials Represented as Linked Lists

1/**
2 * Definition for a polynomial singly-linked list node.
3 */
4class PolyNode {
5    int coefficient, power;
6    PolyNode next = null;
7
8    // Constructors
9    PolyNode() {}
10    PolyNode(int x, int y) { this.coefficient = x; this.power = y; }
11    PolyNode(int x, int y, PolyNode next) { this.coefficient = x; this.power = y; this.next = next; }
12}
13
14class Solution {
15    /**
16     * Adds two polynomials represented as linked lists.
17     * @param poly1 First polynomial represented as a linked list.
18     * @param poly2 Second polynomial represented as a linked list.
19     * @return The result of the polynomial addition, also as a linked list.
20     */
21    public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
22        // dummy node to simplify list operations
23        PolyNode dummyNode = new PolyNode();
24        // iterator for the resultant list
25        PolyNode current = dummyNode;
26      
27        // Iterate over both polynomial linked lists
28        while (poly1 != null && poly2 != null) {
29            if (poly1.power > poly2.power) {
30                // The term from poly1 should come next in the result list
31                current.next = poly1;
32                poly1 = poly1.next;
33            } else if (poly1.power < poly2.power) {
34                // The term from poly2 should come next in the result list
35                current.next = poly2;
36                poly2 = poly2.next;
37            } else {
38                // Powers are equal, sum the coefficients
39                int sumCoefficient = poly1.coefficient + poly2.coefficient;
40                if (sumCoefficient != 0) { // Only add non-zero terms to the result
41                    current.next = new PolyNode(sumCoefficient, poly1.power);
42                }
43                // Move forward in both lists
44                poly1 = poly1.next;
45                poly2 = poly2.next;
46            }
47            // Don't move current in the case where sumCoefficient is zero to avoid zero coefficient terms in the list
48            if (current.next != null) {
49                current = current.next;
50            }
51        }
52      
53        // If there's remaining terms in poly1 or poly2, append them to the result
54        current.next = (poly1 != null) ? poly1 : poly2;
55      
56        // The first node is dummy, so return the next node which is the head of the actual result
57        return dummyNode.next;
58    }
59}
60

1/**
2 * Definition for polynomial singly-linked list.
3 * This structure is used for representing terms in a polynomial expression
4 * where 'coefficient' represents the term's coefficient and 'power' represents
5 * the term's exponent. The linked list is sorted in decreasing order of powers.
6 */
7struct PolyNode {
8    int coefficient, power;
9    PolyNode *next;
10    PolyNode() : coefficient(0), power(0), next(nullptr) {};
11    PolyNode(int x, int y) : coefficient(x), power(y), next(nullptr) {};
12    PolyNode(int x, int y, PolyNode* next) : coefficient(x), power(y), next(next) {};
13};
14
15class Solution {
16public:
17    /**
18     * Adds two polynomial expressions represented by linked lists.
19     * @param poly1 First polynomial linked list
20     * @param poly2 Second polynomial linked list
21     * @return A new polynomial linked list representing the sum of poly1 and poly2.
22     */
23    PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
24        // Dummy node to simplify edge cases and to keep a reference to list start
25        PolyNode* dummyHead = new PolyNode();
26        PolyNode* current = dummyHead;
27      
28        while (poly1 && poly2) {
29            if (poly1->power > poly2->power) {
30                // If poly1 has a term with greater exponent, append it next in the result
31                current->next = poly1;
32                poly1 = poly1->next;
33            } else if (poly1->power < poly2->power) {
34                // If poly2 has a term with greater exponent, append it next in the result
35                current->next = poly2;
36                poly2 = poly2->next;
37            } else {
38                // If both have the same exponent, sum the coefficients
39                int sumCoefficient = poly1->coefficient + poly2->coefficient;
40                if (sumCoefficient != 0) {
41                    // Append the new term if the sum is non-zero
42                    current->next = new PolyNode(sumCoefficient, poly1->power);
43                    current = current->next;
44                }
45                // Move forward in both lists
46                poly1 = poly1->next;
47                poly2 = poly2->next;
48            }
49            // Move forward in the result list if we appended a term
50            if (current->next) {
51                current = current->next;
52            }
53        }
54      
55        // Append any remaining terms from either polynomial to the result
56        current->next = (poly1 != nullptr) ? poly1 : poly2;
57      
58        // Return the next of dummyHead which points to the start of the sum list
59        PolyNode* headOfSum = dummyHead->next;
60        delete dummyHead; // Clear the memory occupied by the dummy node
61        return headOfSum;
62    }
63};
64

1// Define a class for a polynomial node.
2class PolyNode {
3    coefficient: number;
4    power: number;
5    next: PolyNode | null;
6
7    constructor(x: number = 0, y: number = 0, next: PolyNode | null = null) {
8        this.coefficient = x;
9        this.power = y;
10        this.next = next;
11    }
12}
13
14/**
15 * Adds two polynomial singly-linked lists and returns the sum as a new polynomial singly-linked list.
16 * @param poly1 The first polynomial singly-linked list.
17 * @param poly2 The second polynomial singly-linked list.
18 * @return The sum of poly1 and poly2 as a new polynomial singly-linked list.
19 */
20const addPoly = (poly1: PolyNode | null, poly2: PolyNode | null): PolyNode | null => {
21    // Create a dummy node to serve as the anchor for the result list.
22    const dummy = new PolyNode();
23    // This will be used to iterate over the new polynomial linked list.
24    let current = dummy;
25
26    // Iterate over both polynomials as long as there are nodes in each list.
27    while (poly1 && poly2) {
28        if (poly1.power > poly2.power) {
29            // If the current term of poly1 has a greater power, include it in the result.
30            current.next = poly1;
31            current = current.next;
32            poly1 = poly1.next; // Move to the next term in poly1.
33        } else if (poly1.power < poly2.power) {
34            // If the current term of poly2 has a greater power, include it in the result.
35            current.next = poly2;
36            current = current.next;
37            poly2 = poly2.next; // Move to the next term in poly2.
38        } else {
39            // If the powers are equal, add the coefficients if non-zero and include in the result.
40            const sumOfCoefficients = poly1.coefficient + poly2.coefficient;
41            if (sumOfCoefficients != 0) {
42                current.next = new PolyNode(sumOfCoefficients, poly1.power);
43                current = current.next;
44            }
45            // Move to the next terms in both poly1 and poly2.
46            poly1 = poly1.next;
47            poly2 = poly2.next;
48        }
49    }
50
51    // Attaching the remaining elements of poly1 or poly2 in case one is longer than the other.
52    current.next = poly1 || poly2;
53
54    // The first node in our resulting linked list is a dummy node,
55    // so we return the next node which starts the resulting polynomial.
56    return dummy.next;
57};
58