LeetCode 1634 - Add Two Polynomials Represented as Linked Lists

This problem asks us to add two polynomials represented as singly linked lists. Each node in the linked list represents a single term of a polynomial, with a coefficient and a power.

leetcodemediumlinked-listmathtwo-pointers

LeetCode Problem 1634

Difficulty: 🟡 Medium
Topics: Linked List, Math, Two Pointers

Solution

Problem Understanding

This problem asks us to add two polynomials represented as singly linked lists. Each node in the linked list represents a single term of a polynomial, with a coefficient and a power. The linked list is sorted in strictly descending order of powers, and terms with zero coefficients do not appear. For example, the polynomial 2x^2 + 4x + 3 would be represented as [[2,2],[4,1],[3,0]].

The inputs are the heads of two such linked lists, poly1 and poly2, and we are to produce a new linked list that represents the sum of these polynomials, also in descending order by power, omitting terms whose coefficient becomes zero.

The constraints tell us that each polynomial can have up to 10,000 terms, coefficients can be very large in magnitude (up to 10^9), and powers can also be very large (up to 10^9). However, the lists are strictly decreasing in power, and no coefficient is initially zero.

Edge cases include completely disjoint powers, terms that cancel each other out producing zero coefficients, and empty polynomials. The problem guarantees that input lists are sorted, which is crucial for an efficient solution.

Approaches

The brute-force approach is to traverse each polynomial and insert each term into a dictionary keyed by power. Then, sum the coefficients for terms with the same power and reconstruct a new linked list in descending order. This works but requires sorting the powers at the end, giving an O(n log n) time complexity and extra space for the dictionary.

The optimal approach leverages the fact that the input lists are already sorted in descending order by power. Using a two-pointer technique, we can traverse both lists simultaneously, comparing powers at each step. If the powers are equal, we sum the coefficients. If one power is greater, we append that term to the result. This preserves the descending order naturally and avoids extra sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Uses a dictionary to sum terms, then sorts powers
Optimal O(n + m) O(1) Two-pointer traversal without extra sorting

Algorithm Walkthrough

  1. Initialize a dummy node to serve as the head of the result linked list. Use a pointer current to track the end of the result list as we build it.
  2. Initialize two pointers, p1 and p2, to the heads of poly1 and poly2.
  3. While both p1 and p2 are not null:
  • Compare the powers p1.power and p2.power.
  • If p1.power > p2.power, append p1 to the result and move p1 forward.
  • If p1.power < p2.power, append p2 to the result and move p2 forward.
  • If p1.power == p2.power, sum the coefficients. If the sum is not zero, create a new node with the summed coefficient and the same power, then append it to the result. Move both p1 and p2 forward.
  1. After the loop, append any remaining nodes from p1 or p2 to the result.
  2. Return dummy.next as the head of the new polynomial.

Why it works:

The two-pointer technique guarantees that we process all terms in descending order of power. Terms with the same power are combined, and terms with zero coefficients are omitted. The result remains sorted without additional sorting.

Python Solution

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

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

        while p1 and p2:
            if p1.power > p2.power:
                current.next = PolyNode(p1.coefficient, p1.power)
                p1 = p1.next
            elif p1.power < p2.power:
                current.next = PolyNode(p2.coefficient, p2.power)
                p2 = p2.next
            else:
                summed_coeff = p1.coefficient + p2.coefficient
                if summed_coeff != 0:
                    current.next = PolyNode(summed_coeff, p1.power)
                p1 = p1.next
                p2 = p2.next
            if current.next:
                current = current.next

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

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

        return dummy.next

This implementation mirrors the algorithm. We use a dummy node to simplify appending. The while loop compares powers to decide which node to append. When powers match, we sum coefficients and only append if nonzero. Remaining nodes are appended afterward.

Go Solution

type PolyNode struct {
    Coefficient int
    Power       int
    Next        *PolyNode
}

func addPoly(poly1 *PolyNode, poly2 *PolyNode) *PolyNode {
    dummy := &PolyNode{}
    current := dummy
    p1, p2 := poly1, poly2

    for p1 != nil && p2 != nil {
        if p1.Power > p2.Power {
            current.Next = &PolyNode{Coefficient: p1.Coefficient, Power: p1.Power}
            p1 = p1.Next
        } else if p1.Power < p2.Power {
            current.Next = &PolyNode{Coefficient: p2.Coefficient, Power: p2.Power}
            p2 = p2.Next
        } else {
            sum := p1.Coefficient + p2.Coefficient
            if sum != 0 {
                current.Next = &PolyNode{Coefficient: sum, Power: p1.Power}
            }
            p1 = p1.Next
            p2 = p2.Next
        }
        if current.Next != nil {
            current = current.Next
        }
    }

    for p1 != nil {
        current.Next = &PolyNode{Coefficient: p1.Coefficient, Power: p1.Power}
        current = current.Next
        p1 = p1.Next
    }

    for p2 != nil {
        current.Next = &PolyNode{Coefficient: p2.Coefficient, Power: p2.Power}
        current = current.Next
        p2 = p2.Next
    }

    return dummy.Next
}

In Go, the main difference is the use of nil instead of None and explicit struct initialization. The logic and flow are identical to Python.

Worked Examples

Example 1

Input: poly1 = [[1,1]], poly2 = [[1,0]]

Initial pointers: p1=1x^1, p2=1x^0

Compare powers: 1 > 0, append 1x^1

Advance p1 → None

Append remaining p2=1x^0

Output: [[1,1],[1,0]]

Example 2

Input: poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]

Stepwise:

p1 p2 Action Result List
2x^2 3x^2 sum=5 5x^2
4x^1 -4x^1 sum=0 skip
3x^0 -1x^0 sum=2 2x^0

Output: [[5,2],[2,0]]

Example 3

Input: poly1 = [[1,2]], poly2 = [[-1,2]]

Sum of powers 2: 1 + (-1) = 0 → skip

No remaining nodes

Output: []

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each list is traversed once, where n and m are the lengths of poly1 and poly2
Space O(1) Only pointers and result list are used; we do not use extra space proportional to input

The complexity is optimal given that we must inspect every term once.

Test Cases

# Provided examples
assert addPoly(create_poly([[1,1]]), create_poly([[1,0]])) == [[1,1],[1,0]]  # simple addition
assert addPoly(create_poly([[2,2],[4,1],[3,0]]), create_poly([[3,2],[-4,1],[-1,0]])) == [[5,2],[2,0]]  # cancellation of middle term
assert addPoly(create_poly([[1,2]]), create_poly([[-1,2]])) == []  # complete