Add Two Polynomials Represented as Linked Lists

Add Two Polynomials Represented as Linked Lists - Problem

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 9x⁴ is 9.
power: an integer representing the exponent. The power of the term 9x⁴ 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 5x³ + 4x - 7 is represented by the polynomial linked list with nodes [[5,3],[4,1],[-7,0]].

The polynomial linked list must be in its standard form:

The polynomial must be in strictly descending order by its power value.
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 5x³ + 4x - 7 would be represented as: [[5,3],[4,1],[-7,0]].

Input & Output

Example 1 — Basic Addition

$ Input: poly1 = [[1,2],[2,1]], poly2 = [[6,2],[4,1]]

› Output: [[7,2],[6,1]]

💡 Note: Both polynomials have terms with powers 2 and 1. For power 2: 1 + 6 = 7. For power 1: 2 + 4 = 6. Result is 7x² + 6x.

Example 2 — Different Powers

$ Input: poly1 = [[1,3]], poly2 = [[1,2],[1,1]]

› Output: [[1,3],[1,2],[1,1]]

💡 Note: No common powers, so all terms appear in the result: x³ + x² + x.

Example 3 — Coefficients Cancel Out

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

› Output: [[3,1],[1,0]]

💡 Note: Power 2 terms cancel: 2 + (-2) = 0, so only 3x + 1 remains.

Constraints

0 ≤ m, n ≤ 10⁴
-10⁹ ≤ poly1[i].coefficient, poly2[i].coefficient ≤ 10⁹
poly1[i].power > poly1[i+1].power
poly2[i].power > poly2[i+1].power

Visualization

Tap to expand

Understanding the Visualization

Input

Two polynomials represented as linked lists in descending power order

Process

Add coefficients of terms with same power, keep unique terms

Output

New polynomial with combined terms in descending power order

Key Takeaway

🎯 Key Insight: Use two pointers to merge polynomials like sorted lists, comparing powers and combining coefficients

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use two pointers to merge the polynomials like merging two sorted lists, comparing powers and adding coefficients for equal powers. The optimal two-pointer approach achieves O(m+n) time and O(m+n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Merge	O(m+n)	O(m+n)	Use two pointers to traverse both polynomials simultaneously, merging by power
Convert to Arrays and Reconstruct	O((m+n) log(m+n))	O(m+n)	Convert both linked lists to arrays, combine all terms, then sort and merge

Two Pointers Merge — Algorithm Steps

Initialize two pointers at the heads of both polynomials
Compare powers at current positions
Add term with higher power to result, advance that pointer
If powers are equal, add coefficients and advance both pointers
Continue until both pointers reach the end

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Powers

Compare powers at current positions of both pointers

Add Higher Power

Add term with higher power to result, advance that pointer

Merge Equal Powers

When powers are equal, add coefficients together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct PolyNode {
    int coefficient;
    int power;
    struct PolyNode* next;
};

struct PolyNode* createNode(int coeff, int power) {
    struct PolyNode* node = malloc(sizeof(struct PolyNode));
    node->coefficient = coeff;
    node->power = power;
    node->next = NULL;
    return node;
}

int** solution(int** poly1, int poly1Size, int** poly2, int poly2Size, int* returnSize) {
    // Simplified implementation for two pointers approach
    int maxSize = poly1Size + poly2Size;
    int** result = malloc(maxSize * sizeof(int*));
    int count = 0;
    
    int i = 0, j = 0;
    while (i < poly1Size && j < poly2Size) {
        if (poly1[i][1] > poly2[j][1]) {
            result[count] = malloc(2 * sizeof(int));
            result[count][0] = poly1[i][0];
            result[count][1] = poly1[i][1];
            i++;
        } else if (poly1[i][1] < poly2[j][1]) {
            result[count] = malloc(2 * sizeof(int));
            result[count][0] = poly2[j][0];
            result[count][1] = poly2[j][1];
            j++;
        } else {
            int coeffSum = poly1[i][0] + poly2[j][0];
            if (coeffSum != 0) {
                result[count] = malloc(2 * sizeof(int));
                result[count][0] = coeffSum;
                result[count][1] = poly1[i][1];
            } else {
                count--;
            }
            i++;
            j++;
        }
        count++;
    }
    
    *returnSize = count;
    return result;
}

int main() {
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m+n)

Single pass through both polynomials of length m and n

✓ Linear Growth

Space Complexity

O(m+n)

Result polynomial can have at most m+n terms

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Merge — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler