LeetCode Solutions Blog

Add Two Polynomials Represented as Linked Lists

Number: 1774

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given two polynomial linked lists poly1 and poly2, where each node represents a term of the polynomial (with a coefficient and a power), add these two polynomials and return the resulting polynomial as a linked list in standard form (strictly descending order by power and excluding any term with a coefficient of 0).

Key Insights

The linked lists are sorted in descending order by power.
Use two pointers to traverse both lists simultaneously.
When both nodes have the same power, add the coefficients.
If one list's current node has a higher power than the other's, take that node directly.
Omit any term that becomes 0 after adding coefficients.
Edge case: if the sum is 0, return an empty list.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of poly1 and poly2 respectively. Space Complexity: O(n + m) in the worst-case scenario for the resulting linked list.

Solution

Use two pointers to traverse poly1 and poly2. Compare the power of the nodes:

If poly1.power > poly2.power, append poly1's node to the result and move poly1 forward.
If poly1.power < poly2.power, append poly2's node and move poly2 forward.
If the powers are equal, sum the coefficients and if the result is non-zero, append a new node with this sum. Continue until both lists are exhausted, appending any remaining nodes from the non-empty list. The dummy head trick simplifies managing the result list.

Code Solutions

# Definition for polynomial linked list node.
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:
        # Create a dummy head to simplify list operations.
        dummy = PolyNode(0, 0)
        current = dummy

        # Process both lists until one of them is exhausted.
        while poly1 and poly2:
            if poly1.power > poly2.power:
                current.next = PolyNode(poly1.coefficient, poly1.power)
                poly1 = poly1.next
            elif poly1.power < poly2.power:
                current.next = PolyNode(poly2.coefficient, poly2.power)
                poly2 = poly2.next
            else:
                # Same power: add coefficients.
                sum_coef = poly1.coefficient + poly2.coefficient
                if sum_coef != 0:
                    current.next = PolyNode(sum_coef, poly1.power)
                poly1 = poly1.next
                poly2 = poly2.next
            # Move the pointer if a node was appended.
            if current.next:
                current = current.next

        # Append any remaining nodes.
        while poly1:
            current.next = PolyNode(poly1.coefficient, poly1.power)
            current = current.next
            poly1 = poly1.next

        while poly2:
            current.next = PolyNode(poly2.coefficient, poly2.power)
            current = current.next
            poly2 = poly2.next

        return dummy.next