Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1634. Add Two Polynomials Represented as Linked Lists - Leetcode Solution

Code Implementation

# Definition for singly-linked list node for polynomial term.
class PolyNode:
    def __init__(self, coefficient=0, power=0, next=None):
        self.coefficient = coefficient
        self.power = power
        self.next = next

class Solution:
    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
        dummy = PolyNode()
        curr = dummy

        while poly1 and poly2:
            if poly1.power == poly2.power:
                coef_sum = poly1.coefficient + poly2.coefficient
                if coef_sum != 0:
                    curr.next = PolyNode(coef_sum, poly1.power)
                    curr = curr.next
                poly1 = poly1.next
                poly2 = poly2.next
            elif poly1.power > poly2.power:
                curr.next = PolyNode(poly1.coefficient, poly1.power)
                curr = curr.next
                poly1 = poly1.next
            else:
                curr.next = PolyNode(poly2.coefficient, poly2.power)
                curr = curr.next
                poly2 = poly2.next

        # Append remaining terms
        while poly1:
            curr.next = PolyNode(poly1.coefficient, poly1.power)
            curr = curr.next
            poly1 = poly1.next
        while poly2:
            curr.next = PolyNode(poly2.coefficient, poly2.power)
            curr = curr.next
            poly2 = poly2.next

        return dummy.next
      
/**
 * Definition for polynomial singly-linked list.
 * struct PolyNode {
 *     int coefficient, power;
 *     PolyNode *next;
 *     PolyNode(): coefficient(0), power(0), next(nullptr) {}
 *     PolyNode(int x, int y): coefficient(x), power(y), next(nullptr) {}
 *     PolyNode(int x, int y, PolyNode *next): coefficient(x), power(y), next(next) {}
 * };
 */
class Solution {
public:
    PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
        PolyNode dummy(0, 0);
        PolyNode* curr = &dummy;

        while (poly1 && poly2) {
            if (poly1->power == poly2->power) {
                int coef = poly1->coefficient + poly2->coefficient;
                if (coef != 0) {
                    curr->next = new PolyNode(coef, poly1->power);
                    curr = curr->next;
                }
                poly1 = poly1->next;
                poly2 = poly2->next;
            } else if (poly1->power > poly2->power) {
                curr->next = new PolyNode(poly1->coefficient, poly1->power);
                curr = curr->next;
                poly1 = poly1->next;
            } else {
                curr->next = new PolyNode(poly2->coefficient, poly2->power);
                curr = curr->next;
                poly2 = poly2->next;
            }
        }
        while (poly1) {
            curr->next = new PolyNode(poly1->coefficient, poly1->power);
            curr = curr->next;
            poly1 = poly1->next;
        }
        while (poly2) {
            curr->next = new PolyNode(poly2->coefficient, poly2->power);
            curr = curr->next;
            poly2 = poly2->next;
        }
        return dummy.next;
    }
};
      
/**
 * Definition for polynomial singly-linked list.
 * class PolyNode {
 *     int coefficient, power;
 *     PolyNode next;
 *     PolyNode() {}
 *     PolyNode(int x, int y) { this.coefficient = x; this.power = y; }
 *     PolyNode(int x, int y, PolyNode next) { this.coefficient = x; this.power = y; this.next = next; }
 * }
 */
class Solution {
    public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
        PolyNode dummy = new PolyNode();
        PolyNode curr = dummy;

        while (poly1 != null && poly2 != null) {
            if (poly1.power == poly2.power) {
                int coef = poly1.coefficient + poly2.coefficient;
                if (coef != 0) {
                    curr.next = new PolyNode(coef, poly1.power);
                    curr = curr.next;
                }
                poly1 = poly1.next;
                poly2 = poly2.next;
            } else if (poly1.power > poly2.power) {
                curr.next = new PolyNode(poly1.coefficient, poly1.power);
                curr = curr.next;
                poly1 = poly1.next;
            } else {
                curr.next = new PolyNode(poly2.coefficient, poly2.power);
                curr = curr.next;
                poly2 = poly2.next;
            }
        }
        while (poly1 != null) {
            curr.next = new PolyNode(poly1.coefficient, poly1.power);
            curr = curr.next;
            poly1 = poly1.next;
        }
        while (poly2 != null) {
            curr.next = new PolyNode(poly2.coefficient, poly2.power);
            curr = curr.next;
            poly2 = poly2.next;
        }
        return dummy.next;
    }
}
      
/**
 * // Definition for singly-linked list for polynomial term.
 * function PolyNode(coefficient, power, next) {
 *     this.coefficient = (coefficient===undefined ? 0 : coefficient)
 *     this.power = (power===undefined ? 0 : power)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {PolyNode} poly1
 * @param {PolyNode} poly2
 * @return {PolyNode}
 */
var addPoly = function(poly1, poly2) {
    let dummy = new PolyNode(0, 0);
    let curr = dummy;
    while (poly1 && poly2) {
        if (poly1.power === poly2.power) {
            let coef = poly1.coefficient + poly2.coefficient;
            if (coef !== 0) {
                curr.next = new PolyNode(coef, poly1.power);
                curr = curr.next;
            }
            poly1 = poly1.next;
            poly2 = poly2.next;
        } else if (poly1.power > poly2.power) {
            curr.next = new PolyNode(poly1.coefficient, poly1.power);
            curr = curr.next;
            poly1 = poly1.next;
        } else {
            curr.next = new PolyNode(poly2.coefficient, poly2.power);
            curr = curr.next;
            poly2 = poly2.next;
        }
    }
    while (poly1) {
        curr.next = new PolyNode(poly1.coefficient, poly1.power);
        curr = curr.next;
        poly1 = poly1.next;
    }
    while (poly2) {
        curr.next = new PolyNode(poly2.coefficient, poly2.power);
        curr = curr.next;
        poly2 = poly2.next;
    }
    return dummy.next;
};

Problem Description

Given two polynomials represented as singly linked lists, where each node contains a coefficient and a power (the exponent), add the two polynomials and return the sum as a new linked list in the same format. The input lists are sorted in descending order of power. Each term with a zero coefficient should be omitted from the result, and you must not reuse or modify the input nodes. There is always one valid solution.

Thought Process

To solve this problem, think of adding polynomials as merging two sorted lists. Each node represents a term, and the power field is like a sorting key. If both lists have a term with the same power, add their coefficients. If the powers are different, keep the term with the larger power. This is similar to merging two sorted arrays or linked lists, but with the additional logic of summing coefficients for matching exponents and skipping zero-coefficient terms.

A brute-force approach would be to convert both polynomials to arrays or hash maps and sum the coefficients by exponents, but since the lists are already sorted, we can do this efficiently in a single pass.

Solution Approach

The optimal solution uses a two-pointer technique, merging the lists as follows:
  • Initialize a dummy node to build the result list.
  • Use two pointers, one for each input list.
  • While both pointers are not null:
    • If the powers are equal, sum the coefficients. If the sum is non-zero, create a new node in the result list.
    • If one power is greater, add that term to the result and advance the corresponding pointer.
  • After one list ends, append the remaining terms from the other list directly.
  • Return the next node after the dummy as the result.
This approach leverages the sorted order of the lists, avoids extra space, and ensures all terms are processed exactly once. Each term is handled in O(1) time.

Example Walkthrough

Suppose poly1 is 5x3 + 4x2 + 2 and poly2 is 5x1 + 5.
Represented as:
  • poly1: (5,3) → (4,2) → (2,0)
  • poly2: (5,1) → (5,0)
Step-by-step:
  1. Compare 3 vs 1: 3 is higher, add (5,3).
  2. Compare 2 vs 1: 2 is higher, add (4,2).
  3. Compare 0 vs 1: 1 is higher, add (5,1).
  4. Compare 0 vs 0: powers equal, sum 2+5=7, add (7,0).
  5. Both lists are now finished.
Final result: (5,3) → (4,2) → (5,1) → (7,0)

Time and Space Complexity

Brute-force: Converting to arrays or hash maps takes O(N+M) time and space, where N and M are the lengths of the input lists.
Optimized (two-pointer): Each node from both lists is visited once, so the time complexity is O(N+M). The space complexity is O(1) extra (not counting the output list), since we only create new nodes for the result.

Summary

By treating the input as sorted lists and merging them with a two-pointer technique, we efficiently add two polynomials in a single pass. The key insight is to process terms in order, sum coefficients for matching powers, and skip zero-coefficient results. This leads to a clean, optimal solution with minimal extra memory.