A polynomial linked list is a special type of linked list where every node represents a term in a polynomial expression.
Each node has three attributes:
coefficient: an integer representing the number multiplier of the term. The coefficient of the term 9x4 is 9.power: an integer representing the exponent. The power of the term 9x4 is 4.next: a pointer to the next node in the list, or null if it is the last node of the list.For example, the polynomial 5x3 + 4x - 7 is represented by the polynomial linked list illustrated below:
The polynomial linked list must be in its standard form: the polynomial must be in strictly descending order by its power value. Also, terms with a coefficient of 0 are omitted.
Given two polynomial linked list heads, poly1 and poly2, add the polynomials together and return the head of the sum of the polynomials.
PolyNode format:
The input/output format is as a list of n nodes, where each node is represented as its [coefficient, power]. For example, the polynomial 5x3 + 4x - 7 would be represented as: [[5,3],[4,1],[-7,0]].
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 <= 109PolyNode.coefficient != 00 <= PolyNode.power <= 109PolyNode.power > PolyNode.next.powerProblem Overview: Two polynomials are stored as Linked List nodes where each node contains a coefficient and power. The lists are sorted by decreasing power. You need to add the two polynomials and return the result as a new linked list, combining terms with the same power and keeping the order intact.
Approach 1: Hash Map Aggregation (O(n + m) time, O(n + m) space)
Traverse both polynomial lists and store coefficients in a hash map keyed by power. For each node, perform a constant-time hash lookup and add the coefficient to the existing value for that power. After processing both lists, extract the keys, sort them in decreasing order of power, and build the resulting linked list. This approach works even if the inputs are not perfectly ordered, but the extra sorting step increases overhead. The method mainly demonstrates understanding of polynomial representation and aggregation but does not fully exploit the sorted structure of the input. The list traversal itself still relies on basic Linked List iteration.
Approach 2: Two-Pointer Merge (O(n + m) time, O(1) extra space)
The optimal strategy treats the two polynomial lists like the merge step of merge sort. Use two pointers, one for each list. Compare the powers at the current nodes. If the powers match, add the coefficients and create a node only if the sum is non-zero, then advance both pointers. If one power is larger, append that node to the result and move that pointer forward. This works because the lists are already sorted by decreasing power. The algorithm performs a single pass through both lists and builds the result incrementally. It relies on pointer manipulation typical in Two Pointers problems and maintains the mathematical structure of polynomial addition from Math. No additional data structures are required besides the output list.
Recommended for interviews: The two-pointer merge approach is what interviewers expect. It shows you recognized the sorted structure and used it to achieve O(n + m) time with O(1) extra space. The hash map method still demonstrates the core idea of combining coefficients but wastes memory and ignores ordering, which makes it less efficient.
Python
Java
C++
JavaScript
C#
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Aggregation | O(n + m + k log k) | O(n + m) | When polynomial terms may not be sorted or when simplicity is preferred over optimal memory use |
| Two-Pointer Merge | O(n + m) | O(1) | Best choice when both polynomial lists are sorted by power, which matches the problem constraints |
1634. Add Two Polynomials Represented as Linked Lists (Leetcode Medium) • Programming Live with Larry • 250 views views
Watch 5 more video solutions →Practice Add Two Polynomials Represented as Linked Lists with our built-in code editor and test cases.
Practice on FleetCode