Siva Kumar - 1 year ago 36

Java Question

While solving the problem that reverse first K elements of linked list i have written the below recursive code but the last iteration executing twice i.e for k=1, function call reverseNode() happening twice. Can any body why it happening like that. Please correct me if i did any thing wrong in it.

`Example :`

If input is

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

and k = 4 then output is

4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7 -> 8

public void reverseListRecursion(int k) {

this.reverseNode(null, headNode,k);

}

public void reverseNode(Node node, Node nextNode,int k) {

while (k > 0) {

k = k-1;

this.reverseNode(node, nextNode.next,k);

}

if (k == 0) {

this.kNode = nextNode;

this.kNode.next = null;

}

if (node == null) {

nextNode.next = this.kNode;

} else {

nextNode.next = node;

}

}

Working code for my logic it is working expected. but when i try to use variable "k" in "if" condition instead of "presentCounter" then it is going wrong. Can any body tell me the reason.

`public void reverseListRecursion(int count) {`

this.reverseNode(null, headNode, count);

System.out.println("\n");

this.display(this.headNode);

}

/*

* Condition K <= Length of linked list.

*/

public void reverseNode(Node node, Node nextNode, int k) {

int presentCounter = k;

if (k > 1) {

k = k - 1;

this.reverseNode(nextNode, nextNode.next, k);

}

if (presentCounter == 1) {

this.kNode = nextNode.next; // Saving K's Next Node

this.headNode = nextNode; // Setting K node as head node

}

if (node == null) {

nextNode.next = this.kNode;

} else

nextNode.next = node;

}

Answer Source

Your recursion should be

```
if (k > 0) { // and not while
k = k-1;
this.reverseNode(node, nextNode.next,k);
}
...
```