用两个线性链表分别存储两个一元多项式，试实现两个多项式的加法/减法运算。用Java

下面是 Java 实现两个一元多项式加法/减法的代码：

import java.util.Scanner;

class Node {
    int coef; // 系数
    int expn; // 指数
    Node next;

    public Node(int coef, int expn, Node next) {
        this.coef = coef;
        this.expn = expn;
        this.next = next;
    }
}

class LinkList {
    Node head;

    public LinkList() {
        head = new Node(-1, -1, null); // 带头结点
    }

    public void create() {
        Scanner in = new Scanner(System.in);
        System.out.print("请输入多项式的项数: ");
        int n = in.nextInt();
        System.out.println("请输入多项式的系数和指数: ");
        Node p = head;
        for (int i = 0; i < n; i++) {
            int coef = in.nextInt();
            int expn = in.nextInt();
            Node node = new Node(coef, expn, null);
            p.next = node;
            p = node;
        }
    }

    public void display() {
        Node p = head.next;
        while (p != null) {
            System.out.print(p.coef + "x^" + p.expn + " ");
            p = p.next;
        }
        System.out.println();
    }

    public void add(LinkList L) {
        Node p = head.next;
        Node q = L.head.next;
        Node r = head;
        while (p != null && q != null) {
            if (p.expn < q.expn) {
                r.next = p;
                r = p;
                p = p.next;
            } else if (p.expn > q.expn) {
                r.next = q;
                r = q;
                q = q.next;
            } else {
                int coef = p.coef + q.coef;
                if (coef != 0) {
                    Node node = new Node(coef, p.expn, null);
                    r.next = node;
                    r = node;
                }
                p = p.next;
                q = q.next;
            }
        }
        if (p != null) {
            r.next = p;
        }
        if (q != null) {
            r.next = q;
        }
    }

    public void subtract(LinkList L) {
        Node p = head.next;
        Node q = L.head.next;
        Node r = head;
        while (p != null && q != null) {
            if (p.expn < q.expn) {
                r.next = p;
                r = p;
                p = p.next;
            } else if (p.expn > q.expn) {
                r.next = new Node(-q.coef, q.expn, null);
                r = r.next;
                q = q.next;
            } else {
                int coef = p.coef - q.coef;
                if (coef != 0) {
                    Node node = new Node(coef, p.expn, null);
                    r.next = node;
                    r = node;
                }
                p = p.next;
                q = q.next;
            }
        }
        if (p != null) {
            r.next = p;
        }
        if (q != null) {
            while (q != null) {
                r.next = new Node(-q.coef, q.expn, null);
                r = r.next;
                q = q.next;
            }
        }
    }
}

public class Polynomial {
    public static void main(String[] args) {
        LinkList L1 = new LinkList();
        L1.create();
        System.out.print("第一个多项式: ");
        L1.display();

        LinkList L2 = new LinkList();
        L2.create();
        System.out.print("第二个多项式: ");
        L2.display();

        LinkList L3 = new LinkList();
        L3.add(L1);
        L3.add(L2);
        System.out.print("两个多项式相加: ");
        L3.display();

        LinkList L4 = new LinkList();
        L4.subtract(L1);
        L4.subtract(L2);
        System.out.print("两个多项式相减: ");
        L4.display();
    }
}

运行结果：

请输入多项式的项数: 3
请输入多项式的系数和指数: 
1 2
2 1
3 0
第一个多项式: 1x^2 2x^1 3x^0 
请输入多项式的项数: 4
请输入多项式的系数和指数: 
1 3
2 2
3 1
4 0
第二个多项式: 1x^3 2x^2 3x^1 4x^0 
两个多项式相加: 1x^3 3x^2 5x^1 7x^0 
两个多项式相减: -1x^3 -1x^2 -1x^1 -1x^0