Siva Kumar Siva Kumar - 7 months ago 9
Java Question

Reversing first K nodes of Linked List,Why recursion executing twice for last iteration

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

Your recursion should be

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