Add two polynomials represented as linked lists

Linked List Math Two Pointers

61.0% acceptance

Mar 31, 2026

173

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

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

/**
 * 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;
    PolyNode* curr = &dummy;
    while (poly1 && poly2) {
      if (poly1->power > poly2->power) {
        curr->next = poly1;
        poly1 = poly1->next;
      } else if (poly1->power < poly2->power) {
        curr->next = poly2;
        poly2 = poly2->next;
      } else {
        int coeff = poly1->coefficient + poly2->coefficient;
        if (coeff != 0) {
          curr->next = new PolyNode(coeff, poly1->power);
          curr = curr->next;
        }
        poly1 = poly1->next;
        poly2 = poly2->next;
        continue;
      }
      curr = curr->next;
    }
    curr->next = poly1 ? poly1 : poly2;
    return dummy.next;
  }
};