Skip to main content
Talentd

Add Two Polynomials Represented as Linked Lists - Solution & Explanation

MediumPremiumFree on FleetCodeLinked ListMathTwo Pointers7 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 109
  • PolyNode.coefficient != 0
  • 0 <= PolyNode.power <= 109
  • PolyNode.power > PolyNode.next.power

Approach Overview

Problem 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.

Solution

Code

PythonJavaC++JavaScriptC#

Python

Java

C++

JavaScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map AggregationO(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 MergeO(n + m)O(1)Best choice when both polynomial lists are sorted by power, which matches the problem constraints

Video Solution

1634. Add Two Polynomials Represented as Linked Lists (Leetcode Medium) • Programming Live with Larry • 260 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Add Two Polynomials Represented as Linked Lists easy or hard?
This problem is generally classified as Medium difficulty. The challenge comes from correctly merging nodes while handling equal powers and maintaining sorted order. Candidates comfortable with linked list traversal and two-pointer techniques usually solve it quickly.
Add Two Polynomials Represented as Linked Lists Python/Java solution
The typical implementation uses two pointers iterating through both linked lists while constructing a result list. The logic is identical across Python, Java, C++, and JavaScript: compare powers, merge matching terms, and append remaining nodes once one list ends.
How to solve Add Two Polynomials Represented as Linked Lists in O(n)?
Use two pointers to traverse both polynomial lists simultaneously. Compare the powers of the current nodes: if equal, sum the coefficients; otherwise append the node with the larger power. Continue until both lists are fully processed, resulting in a single pass through the data.
What is the best approach for Add Two Polynomials Represented as Linked Lists?
The two-pointer merge approach is the most efficient solution. Since both polynomial linked lists are sorted by decreasing power, you can traverse them simultaneously and merge terms with equal powers. This runs in O(n + m) time and uses O(1) extra space besides the result list.
Is Add Two Polynomials Represented as Linked Lists asked at Google/Amazon/Meta?
Polynomial and linked list merge problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test pointer manipulation and algorithmic thinking. Variations of polynomial addition or merging sorted linked lists are common interview patterns.
What data structure is used in Add Two Polynomials Represented as Linked Lists?
The core data structure is a singly linked list where each node stores a coefficient and power of a polynomial term. The optimal solution uses pointer traversal similar to the merge step in merge sort and relies on the sorted order of the lists.
What is the time complexity of Add Two Polynomials Represented as Linked Lists?
The optimal solution runs in O(n + m) time, where n and m are the number of nodes in the two polynomial linked lists. Each node is visited once during the merge process. The space complexity is O(1) excluding the output list.

Ready to solve this problem?

Practice Add Two Polynomials Represented as Linked Lists with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Add Two Numbers II