这个多项式加法的链表实现中的系数有什么问题？

Question

我在Java中使用链表来实现多项式，链表中的每个节点包含两个int值（系数和指数）和一个指针next。

public class Node {
    public int coef;  
    public int exp;  
    public Node next = null;  

    public Node() {
        coef = 0;
        exp = 0;
    }

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

下面的多项式加法方法需要两个头节点并返回结果链表的头节点。

public class PolynList {
    public static Node add(Node link1, Node link2) {
        Node itr1 = link1;
        Node itr2 = link2;
        while (itr2.next != null) {
            Node newNode = new Node(itr2.next.coef, itr2.next.exp);
            itr2 = itr2.next;
//            System.out.println(newNode.coef);

            while (itr1.next != null) {
                if (itr1.next.exp < itr2.exp) {
                    itr1 = itr1.next;
                } else {
                    if (itr1.next.exp == itr2.exp) {
                        itr1.next.coef += itr2.coef;
                    } else {
                        newNode.next = itr1.next;
                        itr1.next = newNode;
                    }
                    break;
                }
            }

            if (itr1.next == null) {
                itr1.next = itr2;
            }
        }
        return link1.next;
    }
}

结果显示结果多项式的系数不正确。另外，我发现了“System.out.println(newNode.coef);”已执行多次，远远超过预期的 while 循环迭代次数。我不明白这里发生了什么。

我试过这个：

public class Main {
    public static void main(String[] args) {
        Node link1 = new Node();
        Node a1 = new Node(2, 1);
        Node a2 = new Node(3, 3);
        Node a3 = new Node(1, 4);
        link1.next = a1;
        a1.next = a2;
        a2.next = a3;
        a3.next = null;

        Node link2 = new Node();
        Node b1 = new Node(5, 2);
        Node b2 = new Node(2, 4);
        Node b3 = new Node(1, 5);
        Node b4 = new Node(3, 6);
        link2.next = b1;
        b1.next = b2;
        b2.next = b3;
        b3.next = b4;
        b4.next = null;

        System.out.println(PolynList.add(link1, link2).coef);
        System.out.println(PolynList.add(link1, link2).exp);
        System.out.println(PolynList.add(link1, link2).next.coef);
        System.out.println(PolynList.add(link1, link2).next.exp);
        System.out.println(PolynList.add(link1, link2).next.next.coef);
        System.out.println(PolynList.add(link1, link2).next.next.exp);
        System.out.println(PolynList.add(link1, link2).next.next.next.coef);
        System.out.println(PolynList.add(link1, link2).next.next.next.exp);
        System.out.println(PolynList.add(link1, link2).next.next.next.next.coef);
        System.out.println(PolynList.add(link1, link2).next.next.next.next.exp);
        System.out.println(PolynList.add(link1, link2).next.next.next.next.next.coef);
        System.out.println(PolynList.add(link1, link2).next.next.next.next.next.exp);
    }
}

结果在这里：

2
1
15
2
3
3
15
4
256
5
6144
6

这正是我所期望的：

2
1
5
2
3
3
3
4
1
5
3
6

Answer 1

我发现您的代码有几个问题：方法

add

修改了输入中给出的多项式，因此您不能在调用后重用它们，您应该有嵌套循环，您的多项式在开头有一个额外的节点。

尝试这样的事情：

public static Node add(Node link1, Node link2) {
    Node first = null;
    Node last = null;
    while (link1 != null && link2 != null) {
        Node newNode;
        if (link1.exp == link2.exp) {
            newNode = new Node(link1.coef + link2.coef, link1.exp);
            link1 = link1.next;
            link2 = link2.next;
        } else if (link1.exp < link2.exp) {
            newNode = new Node(link1.coef, link1.exp);
            link1 = link1.next;
        } else {
            newNode = new Node(link2.coef, link2.exp);
            link2 = link2.next;
        }
        if (last == null) {
            first = last = newNode;
        } else {
            last.next = newNode;
            last = newNode;
        }
    }
    while (link1 != null) {
        Node newNode = new Node(link1.coef, link1.exp);
        link1 = link1.next;
        if (last == null) {
            first = last = newNode;
        } else {
            last.next = newNode;
            last = newNode;
        }
    }
    while (link2 != null) {
        Node newNode = new Node(link2.coef, link2.exp);
        link2 = link2.next;
        if (last == null) {
            first = last = newNode;
        } else {
            last.next = newNode;
            last = newNode;
        }
    }
    return first;
}