Add Two Polynomials Represented as Linked Lists - CPP Solution

1. Introduction

In this blog post, we explore a classic problem in data structures: adding two polynomials represented as linked lists. This problem combines linked list manipulation with basic algebraic operations.

Problem

Given two polynomials represented as singly linked lists, write a function to add these two polynomials and return the sum as a new linked list. Each node in the linked list represents a term in the polynomial, containing the coefficient and the power of the variable.

2. Solution Steps

1. Initialize a new linked list to store the sum of the polynomials.

2. Traverse both polynomial lists simultaneously.

3. For each pair of nodes from the two lists, compare their powers:

- If the powers are equal, add their coefficients and append to the sum list.

- If not, append the node with the higher power to the sum list.

4. Continue the process until both lists are fully traversed.

5. Return the head of the sum list.

3. Code Program

#include <iostream>
using namespace std;

// Node structure for Polynomial
struct PolyNode {
    int coefficient, power;
    PolyNode *next;
    PolyNode(int c, int p) : coefficient(c), power(p), next(nullptr) {}
};

// Function to add two polynomials
PolyNode* addPolynomials(PolyNode* poly1, PolyNode* poly2) {
    PolyNode *sum = new PolyNode(0, 0), *current = sum;

    while (poly1 != nullptr && poly2 != nullptr) {
        if (poly1->power == poly2->power) {
            int coeff = poly1->coefficient + poly2->coefficient;
            if (coeff != 0) {
                current->next = new PolyNode(coeff, poly1->power);
                current = current->next;
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->power > poly2->power) {
            current->next = new PolyNode(poly1->coefficient, poly1->power);
            current = current->next;
            poly1 = poly1->next;
        } else {
            current->next = new PolyNode(poly2->coefficient, poly2->power);
            current = current->next;
            poly2 = poly2->next;
        }
    }

    while (poly1 != nullptr) {
        current->next = new PolyNode(poly1->coefficient, poly1->power);
        current = current->next;
        poly1 = poly1->next;
    }

    while (poly2 != nullptr) {
        current->next = new PolyNode(poly2->coefficient, poly2->power);
        current = current->next;
        poly2 = poly2->next;
    }

    return sum->next;
}

// Function to print the polynomial
void printPolynomial(PolyNode* head) {
    while (head != nullptr) {
        cout << head->coefficient << "x^" << head->power;
        if (head->next != nullptr) cout << " + ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Creating two polynomials: 5x^2 + 4x^1 + 2 and 5x^1 + 5
    PolyNode* poly1 = new PolyNode(5, 2);
    poly1->next = new PolyNode(4, 1);
    poly1->next->next = new PolyNode(2, 0);

    PolyNode* poly2 = new PolyNode(5, 1);
    poly2->next = new PolyNode(5, 0);

    PolyNode* sum = addPolynomials(poly1, poly2);
    printPolynomial(sum); // Expected output: 5x^2 + 9x^1 + 7
    return 0;
}

Output:

5x^2 + 9x^1 + 7

Explanation:

The addPolynomials function creates a new polynomial (linked list) representing the sum of the two given polynomials. 

It traverses both lists, adding coefficients of terms with the same power and appending terms to the result list. If the powers are different, it appends the term with the higher power first. 

After traversing both lists, it returns the head of the new list, which represents the sum of the polynomials.