Recursion of a linked list
When given an array of integers, I try to change each element with integers before it.
For example, int[] array = {2,2,3,4};
now:{2, 4, 12, 48};
I have added each element in LinkedList
and I am trying to do it recursively.
This is what I have:
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);
}
}
The first product works: {2,4}, but when I try to enable recursion, I get stackoverflow. Any suggestions?
Edit: So the reason I get stackoverflow or null pointer exception is because I update the list and then try to get the next integer (but since there are only two items in the list, no getNext()
). I'm not sure how to fix this.
source to share
It looks like you got a little tied to recursion. I changed your method to accept Node
along with the product from the previous iteration. At each step of the iteration, I update the value in the already existing one List
, so there is no need to use the operator 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
}
}
source to share
This is because you are calling a recursive method on the current node, so it never actually gets promoted to the LinkedList. You can just update the following node data and call a recursive method on it. See the code below:
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);
}
}
source to share
There are two problems with the code.
The recursion never ends, i.e. it does not actually jump to the smaller "subproblem", since recursion calls the same node again and again.
After creating a new node and modifying the next one, we also need to connect the node "after" the next node, otherwise the link will be lost. Please see the method below that addresses both issues.
While I haven't done excessive testing, it works for a simple dataset. Original list: 2-> 4-> 5-> 6-> 8-> null Multiple list: 2-> 8-> 40-> 240-> 1920-> null
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);
}
}
source to share