Adding two polynomials using Linked List in Java

2025年3月27日 | 阅读 9 分钟

使用链表表示两个多项式。为了对具有相同变量幂的系数求和，请编写一个函数来添加这些列表。

Adding two polynomials using Linked List in Java

示例 1

输入

int num1 = 7x⁴ + 4x³ + 6x²+ 1x⁰

int num2 = 6x¹ + 4x⁰

输出

相加两个多项式后的结果是 7x⁴ + 4x³ + 6x² + 6x¹ +5x⁰

示例 2

输入

int num1 = 5x² + 4x¹ + 2x⁰

int num2 = -5x¹ - 5x⁰

输出

相加两个多项式后的结果是 5x²- 1x¹- 3x⁰

示例 3

输入

int num1 = 5x³ + 3x² + x⁰

int num2 = 5x¹ - 4x⁰

输出

相加两个多项式后的结果是 5x³ + 3x² + 5x¹ - 3x⁰

方法：朴素方法

通过这个 Java 程序添加表示两个多项式的链表。多项式中每个项的系数和幂都存储在链表的一个节点中。PolynomialAddition 类有一个名为 polynomial 的方法，该方法通过遍历两个输入多项式 ptr1 和 ptr2 的节点来添加具有相同幂的等效项。如果幂不同，则具有较大幂的项将直接添加到结果中。结果是一个新的链表。使用加法函数，在主过程中构建两个多项式，并打印出结果多项式。

算法

步骤 1: 为两个多项式创建链表，每个系数及其对应的幂都包含一个节点。

步骤 2: 从两个多项式的链表头部开始。

步骤 3: 分析两个多项式中当前项的幂。

步骤 3.1: 如果幂相等，则将它们的系数相加，并将一个新节点添加到结果列表中。

步骤 3.2: 如果一个多项式的幂大于另一个，则将其项直接添加到结果列表中。

步骤 4: 如果一个多项式先于另一个结束，则应将另一个多项式的剩余项直接添加到结果列表中。

步骤 5: 打印多项式中的每个项（系数和幂），然后遍历结果链表。

实施

文件名: LinkedListAddingPolynomials.java

import java.io.*; 
import java.util.*;
import java.util.Scanner; 
class PolynomialAddition 
{ 
	public static Node Polynomial(Node ptr1, Node ptr2) 
	{ 
	    // Create a new linked list to hold the result 
	    // and pointers for analyzing both polynomials.
		Node a = ptr1, b = ptr2, newHead = new Node(0, 0), c = newHead; 
		// When one of the polynomials still has terms, 
		// traverse both of them.
		while (a != null || b != null) 
		{ 
		    // Traverse both polynomials if there are any remaining terms.
			if (a == null) 
			{ 
				c.next = b; 
				break; 
			} 
			// Add the first polynomial if there are no more 
			// terms in the second polynomial.
			else if (b == null) 
			{ 
				c.next = a; 
				break; 
			} 
			else if (a.pow == b.pow) // Add the coefficients if the powers of the two terms are the same.
			{ 
				c.next = new Node(a.coefficient + b.coefficient, a.pow); 
				a = a.next; 
				b = b.next; 
			} 
			else if (a.pow > b.pow) // Add the term with a higher power from the first polynomial to the outcome.
			{ 
				c.next = new Node(a.coefficient, a.pow); 
				a = a.next; 
			} 
			else if (a.pow < b.pow) // Add the term with a higher power from the second polynomial to the outcome.
			{ 
				c.next = new Node(b.coefficient, b.pow); 
				b = b.next; 
			} 
			c = c.next; // traverse to the next node
		} 
		return newHead.next; 
	} 
} 
class Node 
{ 
	int coefficient; 
	int pow; 
	Node next; 
	// Constructor to set the node's coefficient and power initialization
	Node(int a, int b) 
	{ 
		coefficient = a; 
		pow = b; 
		next = null; 
	} 
} 
public class LinkedListAddingPolynomials
{ 
	public static void main(String args[]) 
	{ 
		Node s1 = null, current1 = null, s2 = null, current2 = null; 
		int[] list1_coefficient = { 5, 3, 1 }; 
		int[] list1_power = { 3, 2, 0 }; 
		int n = list1_coefficient.length; 
		int i = 0; 
		// Create the first polynomial's linked list.
		while (n-- > 0) 
		{ 
			int a = list1_coefficient[i]; 
			int b = list1_power[i]; 
			Node p = new Node(a, b); 
			if (s1 == null) 
			{ 
				s1 = p; 
				current1 = p; 
			} 
			else { 
				current1.next = p; 
				current1 = p; 
			} 
			i++; 
		} 
		int[] list2_coefficient = { 5, -4 }; 
		int[] list2_power = { 1, 0 }; 
		n = list2_coefficient.length; 
		i = 0; 
		// Create the second polynomial's linked list.
		while (n-- > 0) 
		{ 
			int a = list2_coefficient[i]; 
			int b = list2_power[i]; 
			Node ptr = new Node(a, b); 
			if (s2 == null) 
			{ 
				s2 = ptr; 
				current2 = ptr; 
			} 
			else 
			{ 
				current2.next = ptr; 
				current2 = ptr; 
			} 
			i++; 
		} 
		PolynomialAddition object = new PolynomialAddition(); 
		Node sum = object.Polynomial(s1, s2); 
		Node traverse = sum; 
		System.out.println("The result after adding two polynomials is ");
		while (traverse != null) 
		{ 
			System.out.print(traverse.coefficient + "x^" + traverse.pow); 
			if (traverse.next != null) 
				System.out.print(" + "); 
			traverse = traverse.next; 
		} 
		System.out.println(); 
	} 
}   

输出

 
The result after adding two polynomials is 
5x^3 + 3x^2 + 5x^1 + -3x^0

复杂度分析

时间复杂度为 O(m + n)，其中 m 和 n 分别表示第一个和第二个列表中的节点数。空间复杂度为 O(m+n)，因为两个多项式相加的结果存储在一个大小为 m + n 的新链表中。

朴素方法的简洁版本

为了访问结果链表的最后一个节点，我们将跟踪一个前一个指针。除了生成新节点外，我们还将修改现有的节点。PolynomialAddition 遍历两个链表以执行加法，而 append 方法则将项添加到多项式中。打印包含结果的多项式表达式。为了动态处理具有不同次数的多项式项，使用了链表。

算法

步骤 1: 为第一个和第二个多项式中的每个项创建节点（幂，系数）。

步骤 2: 创建一个虚拟节点以保存结果。

步骤 3: 使用两个多项式的链表形式遍历它们并比较项的幂。

步骤 3.1: 如果幂相等，则将系数相加。

步骤 3.2: 如果一个多项式的幂更大，则将其项直接添加到结果中。

步骤 4: 如果一个多项式处理完毕但另一个多项式仍未完成，则将剩余的项添加到结果中。

步骤 5: 导航结果链表后，打印多项式表达式。

实施

文件名: ConciseAddingPolynomials.java

import java.util.*; 
import java.io.*;
public class ConciseAddingPolynomials
{ 
	public static void main(String args[]) 
	{ 
		// declaring the first polynomial
		Node p1 = new Node(5, 3); 
		append(p1, 3, 2); 
		append(p1, 1, 0); 
		// declaring the second polynomial
		Node p2 = new Node(5, 1); 
		append(p2, -4, 0); 
		Node sum = PolynomialAddition(p1, p2); 
		System.out.println("The result after adding two polynomials is ");
		for (Node p = sum; p != null; p = p.next) 
		{ 
			// printing polynomial 
			System.out.print(p.coefficient + "x^" + p.power); 
			if (p.next != null) 
				System.out.print(" + "); 
		} 
		System.out.println(); 
	} 
	//Insert in a linked list 
	public static void append(Node head, int coefficient, int power) 
	{ 
	    //Create and declare the new node for the term
		Node new_node = new Node(coefficient, power); 
		//Go through the linked list to the end.
		while (head.next != null) 
		{ 
			head = head.next; 
		} 
		// add the newly added term to the linked list's end.
		head.next = new_node; 
	} 
	// The following method prints the necessary polynomial 
	// sums, p1 and p2, as specified in the output. 
	public static Node PolynomialAddition(Node ptr1, Node ptr2) 
	{ 
	    // dummy node ... the head of the resultant linked list 
		Node result = new Node( 0, 0); 
		// pointer to the last node of the resultant linked list
		Node previous = result;  
		while (ptr1 != null && ptr2 != null) 
		{ 
			if (ptr1.power < ptr2.power) 
			{ 
				previous.next = ptr2; 
				previous = ptr2; 
				ptr2 = ptr2.next; 
			} 
			else if (ptr1.power > ptr2.power) 
			{ 
				previous.next = ptr1; 
				previous = ptr1; 
				ptr1 = ptr1.next; 
			} 
			else { 
				ptr1.coefficient = ptr1.coefficient + ptr2.coefficient; 
				previous.next = ptr1; 
				previous = ptr1; 
				ptr1 = ptr1.next; 
				ptr2 = ptr2.next; 
			} 
		} 
		if (ptr1 != null) { 
			previous.next = ptr1; 
		} 
		else if (ptr2 != null) { 
			previous.next = ptr2; 
		} 
		return result.next; 
	} 
} 
class Node 
{ 
	public int coefficient; 
	public int power; 
	public Node next; 
	public Node(int c, int p) 
	{ 
		this.coefficient = c; 
		this.power = p; 
		this.next = null; 
	} 
}    

输出

 
The result after adding two polynomials is 
5x^3 + 3x^2 + 5x^1 + -3x^0

复杂度分析

时间复杂度为 O(m + n)，其中 m 和 n 分别表示第一个和第二个列表中的节点数。空间复杂度为 O(1)。

方法：递归方法

上面的代码中使用链表结构来进行多项式加法。每个多项式项的系数和幂都存储在一个代表该项的节点中。使用 PolynomialAddition 技术，递归地比较两个多项式的项。当两个项具有相同的幂时，在将它们的系数相加后显示结果。剩余的项按顺序打印，具有较高幂的多项式项先打印。使用 insert 方法将一个新项添加到链表中，而 printList 方法通过适当的格式确保有利项以可读的格式显示多项式。

实施

文件名: AdditionPolynomial.java

import java.io.*;
import java.util.*;
public class AdditionPolynomial 
{ 
    public static void main(String[] args) 
    { 
        // First polynomial
        Node h = new Node(5, 3); 
        insert(h, 3, 2); 
        insert(h, 1, 0); 
        // Second polynomial
        Node h2 = new Node(5, 1); 
        insert(h2, -4, 0); 
        printList(h); 
        System.out.println(); 
        printList(h2); 
        System.out.println("\nThe result is given by: "); 
        PolynomialAddition(h, h2); 
    } 
    public static void PolynomialAddition(Node h1, Node h2) 
    { 
        if (h1 == null && h2 == null) 
            return; 
        // Add the coefficients if the powers of 
        // the two terms are the same.
        if (h1 != null && h2 != null && h1.power == h2.power) 
        { 
            int sum = h1.coefficient + h2.coefficient;
            if (sum >= 0 && h1 != h1.next) 
                System.out.print("+ "); // For positive terms (apart from the first term), add "+ "
            System.out.print(sum + "x^" + h1.power + " "); 
            PolynomialAddition(h1.next, h2.next); 
        } 
        // If the term in the first polynomial has a greater power
        else if (h1 != null && (h2 == null || h1.power > h2.power)) 
        { 
            if (h1.coefficient > 0 && h1 != h1.next) 
                System.out.print("+ "); 
            System.out.print(h1.coefficient + "x^" + h1.power + " "); 
            PolynomialAddition(h1.next, h2); 
        } 
        // If the term in the second polynomial has a greater power
        else if (h2 != null) 
        { 
            if (h2.coefficient > 0 && h2 != h2.next) 
                System.out.print("+ "); 
            System.out.print(h2.coefficient + "x^" + h2.power + " "); 
            PolynomialAddition(h1, h2.next); 
        } 
    } 
    // Method for adding a new term to a polynomial
    public static void insert(Node h, int coefficient, int power) 
    { 
        Node new_node = new Node(coefficient, power); 
        while (h.next != null) 
        { 
            h = h.next; 
        } 
        h.next = new_node; 
    } 
    public static void printList(Node h) 
    { 
        System.out.println("The polynomial is: "); 
        boolean first = true;
        while (h != null) 
        { 
            if (!first && h.coefficient > 0) 
                System.out.print("+ "); // For positive terms other than the first, add "+ "
            System.out.print(h.coefficient + "x^" + h.power + " "); 
            first = false;
            h = h.next; 
        } 
    } 
} 
// To represent a term in the polynomial, use the node class
class Node 
{ 
    public int coefficient, power; 
    public Node next; 
    // Initialize a polynomial term using the constructor
    public Node(int coefficient, int power) 
    { 
        this.coefficient = coefficient; 
        this.power = power; 
        this.next = null; 
    } 
}   

输出

 
The polynomial is: 
5x^3 + 3x^2 + 1x^0 
The polynomial is: 
5x^1 -4x^0 
The result is given by: 
+ 5x^3 + 3x^2 + 5x^1 -3x^0

复杂度分析

时间复杂度为 O(m + n)，空间复杂度为 O(m + n)，其中 m 和 n 分别表示第一个和第二个列表中的节点数。

下一个主题Java 中的组合

Adding two polynomials using Linked List in Java

方法：朴素方法

实施

朴素方法的简洁版本

实施

方法：递归方法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Adding two polynomials using Linked List in Java

方法：朴素方法

实施

朴素方法的简洁版本

实施

方法：递归方法

实施

相关帖子

Java 中获取日期范围

strictfp keyword in Java

Java Huffman 编码

Java 中的计数排序

What is programming

Java 中的上下文切换

Java 中查找直线上的最大点数

Java 中的容器化

Transitive Closure of a Graph Using Floyd-Warshall Algorithm in Java

Java 的最佳自动化框架

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器