1634. Add Two Polynomials Represented as Linked Lists

Problem Description

The problem defines a special type of linked list where each node represents a term in a polynomial expression. Here are the key points about the linked list structure and the problem requirements:

Each node contains a coefficient (an integer representing the multiplier) and a power (an integer representing the exponent).
The linked list represents a polynomial in which the terms are in strictly descending order by their power.
Terms with a coefficient of 0 are not included in the list.
The goal is to add two such polynomial linked lists and return the resulting polynomial linked list that maintains the same properties.

For example, two polynomials 5x^3 + 4x - 7 and 3x^3 - 2x + 8 are represented by their respective linked lists. The task is to sum these polynomials to get a new linked list representing the polynomial 8x^3 + 4x + 1.

Intuition

To solve the addition of two polynomials represented by linked lists, we follow these steps:

Create a dummy head for the result polynomial linked list, which helps in easily returning the result.
Traverse both linked lists simultaneously while comparing the powers of the current nodes.
If one polynomial has a higher power term than the other, we add that term to the result list and move to the next term in that polynomial.
If both have terms with the same power, we add the coefficients. If the sum is not zero, we create a new node with this sum and the corresponding power, then add it to the result list.
Continue this process until we reach the end of one or both polynomials.
If there are remaining terms in one of the polynomials, append them to the result list.
Finally, return the next node of the dummy head as it points to the actual head of the result linked list.

By ensuring terms are added in descending order of power, we construct a valid polynomial linked list representing the sum of the input polynomials.

Learn more about Linked List, Math and Two Pointers patterns.

Solution Approach

To implement the solution for adding two polynomial linked lists, here's the step-by-step approach used:

Initial Setup: We use a dummy node approach to simplify the process of building a new linked list. We start with a dummy PolyNode which acts as a placeholder for the head of the new list, and a curr pointer which is used to add new nodes to the list.
```
1dummy = curr = PolyNode()
```
Traversing Both Lists: We use a while loop to iterate through both poly1 and poly2 as long as there are nodes in both lists.
```
1while poly1 and poly2:
```

Power Comparison and Node Addition: Inside the loop, we compare the powers of the current nodes from poly1 and poly2.

If poly1 has a higher power term, we link the current term from poly1 to curr and advance the poly1 pointer.
If poly2 has a higher power term, we do the equivalent by linking poly2 to curr and advancing poly2.
If both terms have the same power, we sum their coefficients and only create and link a new node if the resultant coefficient is not zero. We then advance both pointers.

1if poly1.power > poly2.power:
2    curr.next = poly1
3    poly1 = poly1.next
4elif poly1.power < poly2.power:
5    curr.next = poly2
6    poly2 = poly2.next
7else:
8    if c := poly1.coefficient + poly2.coefficient:
9        curr.next = PolyNode(c, poly1.power)
10    poly1 = poly1.next
11    poly2 = poly2.next

We need to update curr to the next node in the list after adding a node:

1curr = curr.next

Handling Remaining Terms: After the loop, there might be remaining nodes in either poly1 or poly2 if they were not of equal length. We append the remaining nodes to curr.
```
1curr.next = poly1 or poly2
```
Returning the Result: Since dummy is a placeholder with an unused 0 coefficient and 0 power, we return dummy.next, which represents the head of the resultant polynomial linked list.

The overall complexity of the algorithm is linear O(n + m), where n and m are the number of nodes in poly1 and poly2 respectively since each list is only traversed once and nodes are added to the result list in a single pass.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

We will walk through a small example to illustrate the solution approach.

Suppose we have two polynomials represented by linked lists:

poly1 represents 5x^2 + 3x + 1
poly2 represents 2x^2 + x

Represented as linked lists, they would look something like this:

poly1: 5 -> 3 -> 1 (each node has terms decreasing in power from left to right) poly2: 2 -> 1

Steps:

We initiate a dummy node, which will help us in easily building and returning the result.
We begin to iterate through both lists:
- Comparing the powers, 2 and 2 have the same power for the first nodes.
- We add the coefficients (5 + 2) = 7.
- Create a new node with coefficient 7 and power 2 and link it to curr.
- Move both poly1 and poly2 to the next nodes (3 and 1 respectively).
The next comparison:
- poly1 has power 1 and poly2 also has power 1.
- Add coefficients (3 + 1) = 4.
- Create a new node with coefficient 4 and power 1 and link it to curr.
- Move both pointers forward.
Now, poly2 has been completely traversed, but poly1 still has one term left:
- No more comparison is needed.
- Append the last node of poly1 (which is 1) to curr.
The final polynomial linked list, represented by dummy.next, is 7x^2 + 4x + 1.

The constructed linked list will have the following structure, representing the sum of the input polynomials: 7 -> 4 -> 1

Solution Implementation

1# Definition for polynomial singly-linked list.
2class PolyNode:
3    def __init__(self, coefficient=0, power=0, next_node=None):
4        self.coefficient = coefficient
5        self.power = power
6        self.next = next_node
7
8
9class Solution:
10    def addPoly(self, poly1: "PolyNode", poly2: "PolyNode") -> "PolyNode":
11        # Create a dummy node to serve as the head of the result list
12        dummy = current = PolyNode()
13      
14        # Iterate while neither of the polynomial lists is exhausted
15        while poly1 and poly2:
16            # Compare powers of both poly nodes
17            if poly1.power > poly2.power:
18                # If poly1 has the higher power, append it to the result list
19                current.next = poly1
20                poly1 = poly1.next
21            elif poly1.power < poly2.power:
22                # If poly2 has the higher power, append it to the result list
23                current.next = poly2
24                poly2 = poly2.next
25            else:
26                # Both powers are equal, add coefficients if they don't cancel out
27                sum_coefficient = poly1.coefficient + poly2.coefficient
28                if sum_coefficient != 0:
29                    current.next = PolyNode(sum_coefficient, poly1.power)
30                # Move to the next nodes in both lists
31                poly1 = poly1.next
32                poly2 = poly2.next
33
34            # Move to the next node in the result list if we appended a node
35            if current.next: 
36                current = current.next
37
38        # Append the remaining nodes of the polynomial list that is not yet exhausted
39        current.next = poly1 or poly2
40      
41        # Skip the dummy node and return the result list
42        return dummy.next
43
44# Please note that the main method signature of addPoly cannot be changed as it's probably a constraint given by the problem statement.
45

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

Time and Space Complexity

The given code defines a function addPoly that takes two polynomial singly-linked lists as input, where each node represents a term in the polynomial (with a coefficient and power), and returns a new polynomial linked list representing the sum of the two input polynomials.

Time Complexity

The time complexity of this function is O(n + m), where n is the number of terms in poly1 and m is the number of terms in poly2. This is because the function iterates over both lists at most once, advancing one node at a time in whichever list has the term with the higher power, or both if the powers are equal and need to be summed.

Each operation inside the while loop—comparing powers, creating a new node (when coefficients sum to a non-zero value), and linking nodes—occurs in constant time, O(1). Since these operations are not nested and we only iterate through each list once without revisiting any nodes, the time complexity is linear with respect to the total number of nodes in both input lists.

Space Complexity

The space complexity of the function is O(max(n, m)). In the worst-case scenario every term from both polynomials needs to be included in the resulting polynomial. However, since the input polynomials' nodes are reused when possible (i.e., when one term's power is greater than the other or when the sum of coefficients is non-zero), additional space is only required when two terms have the same power and their coefficients sum to a non-zero value, which requires allocating a new node. Therefore, the space complexity depends on the number of such term pairs, which is at most the length of the shorter list, resulting in a space complexity that is the maximum of n or m, excluding any space that may be required for the output.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: