递归中变量的使用

Question

我写了下面的代码来反转链表的前K个节点，它在反转链表的前K个节点时解决了一些问题，为什么递归在最后一次迭代中执行两次，现在它可以正常工作，但为什么它会导致链表中的循环当我尝试在“if”条件下使用变量“k”而不是“PresCouner”时，原因是什么？以及如何避免它？

 /*
 * Condition K <= Length of linked list.
 *  node = null
 *  nextNode headNode of the 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 1

当k为2时，它进入第一个条件（k

然后它会递减k并递归

但是在递归完成后，它将继续到下一行。

k=k-1给出1，因此“if（k==1）”也将在同一遍中执行该第二个条件中的操作。

通过在从presentCounter中减去1之前将k保存到presentCounter中，然后检查presentCounter==1，可以避免两次执行此额外任务（一次在递归调用中执行，因为现在k==1，一次在递归完成时执行）。

Answer 2

因为如果（presenceCount==1），则稍后还会使用presentCounter检查最后一个要交换的元素
如果您天真地摆脱了k，而改用presentCounter

if (presentCounter > 1) {
    presentCounter = presentCounter - 1;
    this.reverseNode(nextNode, nextNode.next, presentCounter);
}

由于现在演示计数器已递减，因此对最后一个要交换的元素的检查会触发之前的一项。

例如，在列表中，当请求交换前三个元素时，应为c进行检查，以便进行交换。旋钮是d型的
如果前一步为true，即对于b，则此步骤为true。旋钮为c（头部设置为b）
当按相反顺序（c b a）链接元素时，旧磁头将链接到此。kNode，所以我们得到了两个不同的结果：

>

Corret（this. kNodeis d）
c b a d

不正确（this. kNode是c）
b a c b a c...

第二个是循环
不过，您可以轻松摆脱k

if (presentCounter > 1)
    this.reverseNode(nextNode, nextNode.next, presentCounter-1);

为了更好的了解是怎么回事，这里放一张图。

您必须了解有两个阶段：遍历阶段（当进行递归调用时）和构建阶段（当递归调用返回时）<因此，每次调用都会被绘制两次。

pc代表presentCounter

¹第一个元素，当node为null时保存在nextNode中的元素，即函数的第一次调用。