Data Modelling & AI Data Structure & Algorithm

Adding two polynomials using Linked List using map

23 June 2025

1

Given two polynomial numbers represented by a linked list. Write a function to perform their algebraic sum. Examples:

Input: 1st number = 5x^2 + 4x^1 + 2x^0 2nd number = 5x^1 + 5x^0 Output: 5x^2 + 9x^1 + 7x^0

Approach: The implementation uses map data structure so that all coefficients of same power value are added together and kept in key-value pairs inside a map. Below is the implementation of the above approach:

CPP

// C++ program for addition of two polynomials
// represented as linked lists
#include <bits/stdc++.h>
using namespace std;
 
// Structure of Node used
struct Node {
 
    // Coefficient of the polynomial
    int coeff;
 
    // Power of the polynomial
    int pow;
    Node* next;
};
 
// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
    struct Node *r, *z;
    z = *temp;
    if (z == NULL) {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        *temp = r;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
    else {
        r->coeff = x;
        r->pow = y;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
}
 
// Display Linked list
void show(struct Node* node)
{
    if (node == NULL)
        return;
    while (node->next != NULL) {
        printf("%dx^%d", node->coeff, node->pow);
        node = node->next;
        if (node->next != NULL)
            printf(" + ");
    }
}
 
/* Function to print the required sum of a
polynomial p1 and p2 as specified in output */
void addPolynomial(Node* p1, Node* p2)
{
    map<int, int> mp;
    Node* temp1 = p1;
    Node* temp2 = p2;
    while (temp1 != NULL) {
 
        // Add coefficients of same power value
        // map contains (powervalue, coeff) pair
        mp[temp1->pow] += temp1->coeff;
        temp1 = temp1->next;
    }
    while (temp2 != NULL) {
        mp[temp2->pow] += temp2->coeff;
        temp2 = temp2->next;
    }
 
    // Started from the end because higher power should
    // come first and there should be "+" symbol in between
    // so iterate up to second element and print last out of
    // the loop.
 
    for (auto it = (mp.rbegin()); it != prev(mp.rend());
         ++it)
        cout << it->second << "x^" << it->first << " + ";
    cout << mp.begin()->second << "x^" << mp.begin()->first;
}
 
// Driver function
int main()
{
    struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
 
    // Create first list of 5x^2 + 4x^1 + 2x^0
    create_node(5, 2, &poly1);
    create_node(4, 1, &poly1);
    create_node(2, 0, &poly1);
 
    // Create second list of 5x^1 + 5x^0
    create_node(5, 1, &poly2);
    create_node(5, 0, &poly2);
 
    printf("1st Number: ");
    show(poly1);
 
    printf("\n2nd Number: ");
    show(poly2);
 
    poly = (struct Node*)malloc(sizeof(struct Node));
 
    printf("\nAdded polynomial: ");
 
    // Function add two polynomial numbers
    addPolynomial(poly1, poly2);
 
    return 0;
}

Java

// Java program for addition of two polynomials
// represented as linked lists
import java.util.*;
 
// Structure of Node used
class Node {
 
    // Coefficient of the polynomial
    int coeff;
 
    // Power of the polynomial
    int pow;
    Node next;
 
    Node(int coeff, int pow) {
        this.coeff = coeff;
        this.pow = pow;
        this.next = null;
    }
}
 
// Display Linked list
class LinkedList {
 
    Node head;
 
    // Function to create new node
    void create_node(int x, int y) {
        Node node = new Node(x, y);
        if (head == null) {
            head = node;
        }
        else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }
 
    void show() {
        Node node = head;
        while (node != null) {
            System.out.print(node.coeff + "x^" + node.pow);
            node = node.next;
            if (node != null) {
                System.out.print(" + ");
            }
        }
    }
}
 
class Main {
 
    // Function to print the required sum of a
    // polynomial p1 and p2 as specified in output
    static void addPolynomial(Node p1, Node p2) {
        Map<Integer, Integer> mp = new TreeMap<>(Collections.reverseOrder());
        Node temp1 = p1;
        Node temp2 = p2;
        while (temp1 != null) {
 
            // Add coefficients of same power value
            // map contains (powervalue, coeff) pair
            mp.put(temp1.pow, mp.getOrDefault(temp1.pow, 0) + temp1.coeff);
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            mp.put(temp2.pow, mp.getOrDefault(temp2.pow, 0) + temp2.coeff);
            temp2 = temp2.next;
        }
 
        // Started from the end because higher power should
        // come first and there should be "+" symbol in between
        // so iterate up to second element and print last out of
        // the loop.
        boolean first = true;
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            int pow = entry.getKey();
            int coeff = entry.getValue();
            if (first) {
                System.out.print(coeff + "x^" + pow);
                first = false;
            } else {
                System.out.print(" + " + coeff + "x^" + pow);
            }
        }
    }
 
    // Driver function
    public static void main(String[] args) {
        LinkedList poly1 = new LinkedList();
        LinkedList poly2 = new LinkedList();
 
        // Create first list of 5x^2 + 4x^1 + 2x^0
        poly1.create_node(5, 2);
        poly1.create_node(4, 1);
        poly1.create_node(2, 0);
 
        // Create second list of 5x^1 + 5x^0
        poly2.create_node(5, 1);
        poly2.create_node(5, 0);
 
        System.out.print("1st Number: ");
        poly1.show();
 
        System.out.print("\n2nd Number: ");
        poly2.show();
 
        System.out.print("\nAdded polynomial: ");
 
        // Function add two polynomial numbers
        addPolynomial(poly1.head, poly2.head);
    }
}
// This code is contributed by Prajwal Kandekar

Python3

# Python program for addition of two polynomials
# represented as linked lists
 
# Structure of Node used
class Node:
    # Coefficient of the polynomial
    def __init__(self, coeff, pow):
        self.coeff = coeff
        # Power of the polynomial
        self.pow = pow
        self.next = None
 
# Function to create new node
def create_node(x, y):
    r = Node(x, y)
    r.next = None
    return r
 
# Display Linked list
def show(node):
    if node is None:
        return
    while node.next is not None:
        print(f"{node.coeff}x^{node.pow}", end="")
        print(" + ", end="")
        node = node.next
        if node.next is not None:
            print(" ", end="")
    print(f"{node.coeff}x^{node.pow}")
 
# Function to print the required sum of a 
# polynomial p1 and p2 as specified in output
def addPolynomial(p1, p2):
    mp = {}
    temp1 = p1
    temp2 = p2
    while temp1 is not None:
        # Add coefficients of same power value
        # map contains (powervalue, coeff) pair
        mp[temp1.pow] = mp.get(temp1.pow, 0) + temp1.coeff
        temp1 = temp1.next
    while temp2 is not None:
        mp[temp2.pow] = mp.get(temp2.pow, 0) + temp2.coeff
        temp2 = temp2.next
 
    # Started from the end because higher power should
    # come first and there should be "+" symbol in between
    # so iterate up to second element and print last out of
    # the loop.
    for power in sorted(mp.keys(), reverse=True):
        print(f"{mp[power]}x^{power}", end="")
        if power != sorted(mp.keys(), reverse=True)[-1]:
            print(" + ", end="")
 
# Driver function
if __name__ == "__main__":
    poly1 = None
    poly2 = None
    poly = None
 
    # Create first list of 5x^2 + 4x^1 + 2x^0
    poly1 = create_node(5, 2)
    poly1.next = create_node(4, 1)
    poly1.next.next = create_node(2, 0)
 
    # Create second list of 5x^1 + 5x^0
    poly2 = create_node(5, 1)
    poly2.next = create_node(5, 0)
 
    print("1st Number: ", end="")
    show(poly1)
 
    print("2nd Number: ", end="")
    show(poly2)
 
    print("Added polynomial: ", end="")
 
    # Function to add two polynomial numbers
    addPolynomial(poly1, poly2)

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
// Structure of Node used
public class Node
{
    // Coefficient of the polynomial
    public int coeff;
 
    // Power of the polynomial
    public int pow;
    public Node next;
}
 
public class PolynomialAddition
{
    // Function to create a new node
    public static Node CreateNode(int x, int y)
    {
        Node r = new Node();
        r.coeff = x;
        r.pow = y;
        r.next = null;
        return r;
    }
 
    // Display Linked list
    public static void Show(Node node)
    {
        if (node == null)
            return;
        while (node.next != null)
        {
            Console.Write($"{node.coeff}x^{node.pow}");
            node = node.next;
            if (node.next != null)
                Console.Write(" + ");
        }
    }
 
    /* Function to print the required sum of a
    polynomial p1 and p2 as specified in output */
    public static void AddPolynomial(Node p1, Node p2)
    {
        Dictionary<int, int> mp = new Dictionary<int, int>();
        Node temp1 = p1;
        Node temp2 = p2;
        while (temp1 != null)
        {
            // Add coefficients of the same power value
            if (!mp.ContainsKey(temp1.pow))
                mp[temp1.pow] = temp1.coeff;
            else
                mp[temp1.pow] += temp1.coeff;
            temp1 = temp1.next;
        }
        while (temp2 != null)
        {
            if (!mp.ContainsKey(temp2.pow))
                mp[temp2.pow] = temp2.coeff;
            else
                mp[temp2.pow] += temp2.coeff;
            temp2 = temp2.next;
        }
 
        // Started from the end because higher power should
        // come first and there should be "+" symbol in between
        // so iterate up to the second element and print the last out of the loop.
 
        foreach (var item in mp.OrderByDescending(x => x.Key))
            Console.Write($"{item.Value}x^{item.Key} + ");
    }
 
    // Driver function
    public static void Main()
    {
        Node poly1 = null;
        Node poly2 = null;
 
        // Create the first list of 5x^2 + 4x^1 + 2x^0
        poly1 = CreateNode(5, 2);
        poly1.next = CreateNode(4, 1);
        poly1.next.next = CreateNode(2, 0);
 
        // Create the second list of 5x^1 + 5x^0
        poly2 = CreateNode(5, 1);
        poly2.next = CreateNode(5, 0);
 
        Console.Write("1st Number: ");
        Show(poly1);
 
        Console.Write("\n2nd Number: ");
        Show(poly2);
 
        Console.Write("\nAdded polynomial: ");
 
        // Function to add two polynomial numbers
        AddPolynomial(poly1, poly2);
    }
}

Javascript

class Node {
    constructor(coeff, pow) {
        this.coeff = coeff;
        this.pow = pow;
        this.next = null;
    }
}
 
// Function to create a new node
function createNode(x, y, temp) {
    let r = new Node(x, y);
    if (temp === null) {
        temp = r;
    } else {
        let current = temp;
        while (current.next !== null) {
            current = current.next;
        }
        current.next = r;
    }
    return temp;
}
 
// Display Linked list
function show(node) {
    if (node === null) {
        return;
    }
    while (node.next !== null) {
        console.log(`${node.coeff}x^${node.pow}`);
        node = node.next;
        if (node.next !== null) {
            console.log(" + ");
        }
    }
}
 
// Function to print the required sum of a polynomial p1 and p2
function addPolynomial(p1, p2) {
    let result = null;
    let currentResult = null;
    let current1 = p1;
    let current2 = p2;
 
    while (current1 !== null && current2 !== null) {
        if (current1.pow === current2.pow) {
            let sumCoeff = current1.coeff + current2.coeff;
            if (sumCoeff !== 0) {
                result = createNode(sumCoeff, current1.pow, result);
                current1 = current1.next;
                current2 = current2.next;
            }
        } else if (current1.pow > current2.pow) {
            result = createNode(current1.coeff, current1.pow, result);
            current1 = current1.next;
        } else {
            result = createNode(current2.coeff, current2.pow, result);
            current2 = current2.next;
        }
    }
 
    // Add any remaining terms from p1 and p2
    while (current1 !== null) {
        result = createNode(current1.coeff, current1.pow, result);
        current1 = current1.next;
    }
 
    while (current2 !== null) {
        result = createNode(current2.coeff, current2.pow, result);
        current2 = current2.next;
    }
 
    // Reverse the result linked list for correct order
    let reversedResult = null;
    while (result !== null) {
        let next = result.next;
        result.next = reversedResult;
        reversedResult = result;
        result = next;
    }
 
    return reversedResult;
}
 
// Driver function
function main() {
    let poly1 = null;
    let poly2 = null;
 
    // Create the first list of 5x^2 + 4x^1 + 2x^0
    poly1 = createNode(5, 2, poly1);
    poly1 = createNode(4, 1, poly1);
    poly1 = createNode(2, 0, poly1);
 
    // Create the second list of 5x^1 + 5x^0
    poly2 = createNode(5, 1, poly2);
    poly2 = createNode(5, 0, poly2);
 
    console.log("1st Number: ");
    show(poly1);
 
    console.log("2nd Number: ");
    show(poly2);
 
    console.log("Added polynomial: ");
    let result = addPolynomial(poly1, poly2);
    show(result);
}
 
main();

Time Complexity: O((m + n)log(m+n)) where m and n are numbers of nodes in first and second lists respectively and we are using a map for adding the coefficients extra log(m+n) factor is added.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

2 COMMENTS

ddiyala 7 December 2025 At 3:36 pm

… [Trackback]

[…] Find More to that Topic: geeksforgeeks.org/adding-two-polynomials-using-linked-list-using-map/ […]

Log in to leave a comment
เว็บตรง สล็อต 8 December 2025 At 4:10 am

… [Trackback]

[…] There you can find 31495 more Info on that Topic: geeksforgeeks.org/adding-two-polynomials-using-linked-list-using-map/ […]

Log in to leave a comment

Adding two polynomials using Linked List using map

CPP

Java

Python3

C#

Javascript

Multimodal RAG Made Simple: RAG-Anything + Milvus Instead of 20 Separate Tools

Introducing the Embedding Function: How Milvus 2.6 Streamlines Vectorization and Semantic Search

Choosing a vector database for ANN search at Reddit

2 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

The Samsung Galaxy Watch feature in One UI 8 I rely on more than my phone

OnePlus 15 Vs. Galaxy S25 Ultra will surprise you. [Video]

Google’s latest update changed the way I feel about NotebookLM

I’m using the Galaxy Tab S11 and Tab S11 Ultra, and here’s what you need to know before buying one

EDITOR PICKS

The Samsung Galaxy Watch feature in One UI 8 I rely on more than my phone

OnePlus 15 Vs. Galaxy S25 Ultra will surprise you. [Video]

Google’s latest update changed the way I feel about NotebookLM

POPULAR POSTS

The Samsung Galaxy Watch feature in One UI 8 I rely on more than my phone

OnePlus 15 Vs. Galaxy S25 Ultra will surprise you. [Video]

Google’s latest update changed the way I feel about NotebookLM

POPULAR CATEGORY

ABOUT US

FOLLOW US