链表的递归

Question

当给定一个整数数组时，我试图用它前面的整数的乘积来改变每个元素。

例如，int[] array = {2,2,3,4};现在是：{2, 4, 12, 48};

我将每个元素都添加到 LinkedList，并且我正在尝试递归执行此操作。

这是我的：

Node curr = list.getFirst();
product(curr);

public static void product(Node curr)
{
    if(curr == null)
    {
        return;
    }
    else
    {
        int data = curr.getData() * curr.getNext().getData();
        Node newNode = new Node(data);
        curr.setNext(newNode);

        //  product(curr);
    }
}

第一个产品有效：{2,4}，但是当我尝试放入递归时，出现计算器溢出。有什么建议吗？？

编辑：所以我得到 Whosebug 或 空指针异常 的原因是因为我正在更新列表，然后尝试获取下一个整数（但由于列表中只有两个元素，因此没有 getNext()）。我不确定如何解决这个问题。

Answer 1

看来您在递归中遇到了一些麻烦。我修改了您的方法以接受 Node 以及上一次迭代的产品。在迭代的每一步，我都会更新已经存在的 List 中的值，因此不需要使用 new 运算符。

public static void product(Node curr, int value) {
    if (curr == null) {
        return;
    }
    else {
        int data = value * curr.getData();  // compute current product
        curr.setData(data);                 // update Node
        product(curr.getNext(), data);      // make recursive call
    }
}

Answer 2

因为你在当前节点上调用了递归方法，所以它实际上是永远不会在LinkedList中向前移动的。您可以简单地更新下一个节点的数据并对其调用递归方法。请看下面的代码：

Node curr = list.getFirst();
product(curr);

public static void product(Node curr)
{
    Node next  = curr.getNext();   
    if(next == null)
    {
        return;
    }
    else
    {
        int data = curr.getData() * next.getData();
        next.setData(data);
        product(next);
    }
}

Answer 3

代码实际上有两个问题。

The recursion never ends, i.e. it is not actually moving to a smaller "subproblem" as the recursion is calling the same node again and again.

After creating a new node and modifying the next we also need to connect the node "after" the next node otherwise the link will be lost. Please check the below method which addresses both the issues.

虽然我没有做过多的测试，但它适用于简单的数据集。原始清单： 2->4->5->6->8->空乘法列表： 2->8->40->240->1920->空

public void product(Node curr) {
    if (curr.getNext() == null) {
        return;
    } else {
        int data = curr.getData() * curr.getNext().getData();
        Node newNode = new Node();
        newNode.setData(data);
        Node nodeAfterNextNode = curr.getNext().getNext();
        newNode.setNext(nodeAfterNextNode);
        curr.setNext(newNode);

        product(newNode);
    }
}

链表的递归

Recursion of Linked List

java

recursion

linked-list

nullpointerexception