链表的递归

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}，但当我尝试放入递归时，我会得到一个stackoverflow。有什么建议吗？？

编辑：所以我得到stackerflow或空指针异常的原因是因为我正在更新列表，然后试图得到下一个整数（但由于列表中只有两个元素，所以没有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

代码实际上有两个问题。

1. 递归永远不会结束，也就是说，当递归再次调用同一节点时，它实际上并没有移动到更小的"子问题"再一次。

2. 在创建一个新节点并修改下一个节点后，我们还需要在"下一个"节点之后连接该节点，否则链接将迷路的请检查以下解决这两个问题的方法。

虽然我没有做过多的测试，但它适用于简单的数据集。原始列表：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);
    }
}

Answer 3

这是因为您在当前节点上调用递归方法，所以它实际上永远不会在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);
    }
}