Java Program For Adding Two Polynomials Using Linked List

0 0 2 minutes read

Given two polynomial numbers represented by a linked list. Write a function that add these lists means add the coefficients who have same variable powers.
Example:

Input:
     1st number = 5x² + 4x¹ + 2x⁰
     2nd number = -5x¹ - 5x⁰
Output:
        5x²-1x¹-3x⁰
Input:
     1st number = 5x³ + 4x² + 2x⁰
     2nd number = 5x^1 - 5x^0
Output:
        5x³ + 4x² + 5x¹ - 3x⁰

Java

import java.io.*;
import java.util.Scanner;
class Polynomial 
{
    public static Node addPolynomial(Node p1, 
                                     Node p2)
    {
        Node a = p1, b = p2, 
             newHead = new Node(0, 0),
             c = newHead;
 
        while (a != null || b != null) 
        {
            if (a == null) 
            {
                c.next = b;
                break;
            }
            else if (b == null) 
            {
                c.next = a;
                break;
            }
 
            else if (a.pow == b.pow) 
            {
                c.next = new Node(a.coeff + 
                                  b.coeff, a.pow);
                a = a.next;
                b = b.next;
            }
 
            else if (a.pow > b.pow) 
            {
                c.next = new Node(a.coeff, 
                                  a.pow);
                a = a.next;
            }
 
            else if (a.pow < b.pow) 
            {
                c.next = new Node(b.coeff, 
                                  b.pow);
                b = b.next;
            }
            c = c.next;
        }
        return newHead.next;
    }
}
 
// Utilities for Linked List 
// Nodes
class Node 
{
    int coeff;
    int pow;
    Node next;
    Node(int a, int b)
    {
        coeff = a;
        pow = b;
        next = null;
    }
}
 
// Linked List main class
class LinkedList 
{  
    public static void main(String args[])
    {
        Node start1 = null, cur1 = null, 
             start2 = null, cur2 = null;
        int[] list1_coeff = {5, 4, 2};
        int[] list1_pow = {2, 1, 0};
        int n = list1_coeff.length;
 
        int i = 0;
        while (n-- > 0) 
        {
            int a = list1_coeff[i];
            int b = list1_pow[i];
            Node ptr = new Node(a, b);
            if (start1 == null) 
            {
                start1 = ptr;
                cur1 = ptr;
            }
            else
            {
                cur1.next = ptr;
                cur1 = ptr;
            }
            i++;
        }
 
        int[] list2_coeff = {-5, -5};
        int[] list2_pow = {1, 0};
        n = list2_coeff.length;
 
        i = 0;
        while (n-- > 0) 
        {
            int a = list2_coeff[i];
            int b = list2_pow[i];
 
            Node ptr = new Node(a, b);
 
            if (start2 == null) 
            {
                start2 = ptr;
                cur2 = ptr;
            }
            else
            {
                cur2.next = ptr;
                cur2 = ptr;
            }
            i++;
        }
 
        Polynomial obj = new Polynomial();
        Node sum = obj.addPolynomial(start1, 
                                     start2);
        Node trav = sum;
        while (trav != null) 
        {
            System.out.print(trav.coeff + 
                             "x^" + trav.pow);
            if (trav.next != null)
                System.out.print(" + ");
            trav = trav.next;
        }
        System.out.println();
    }
}

Output:

1st Number: 5x^2+4x^1+2x^0
2nd Number: -5x^1-5x^0
Added polynomial: 5x^2-1x^1-3x^0

Time Complexity: O(m + n) where m and n are number of nodes in first and second lists respectively.
Auxiliary Space: O(max(m,n) as it is using extra space for resultant linked list.

Please refer complete article on Adding two polynomials using Linked List for more details!

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 zambiatek!