反转链表的前K个节点，为什么在最后一次迭代中执行两次递归

Question

在解决反转链表的前K个元素的问题时，我编写了下面的递归代码，但最后一次迭代执行了两次，即对于K=1，函数调用reverseNode（）发生了两次。任何人都不能解释为什么会这样。如果我做错了什么，请纠正我。

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;
    }
}

工作代码为我的逻辑它是工作的预期。但当我尝试在“if”条件中使用变量“k”而不是“presentCounter”时，它就错了。谁能告诉我原因吗。

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 1

您在问题中提供的此代码有几个问题：

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;
    }
}

>

第一个参数（节点）永远不会改变：递归调用只是传递相同的参数，因此您在初始调用中传递的值（null）就是这个参数在每次调用中的值。因此，最后一个if条件的结果将始终相同。这看起来不太对劲。

第一个if条件将始终为真，因为它与它之前的while条件相反。因此不需要对k==0进行测试。

第一个if块中的代码使this. kNode成为nextNode的同义词，然后它的下一个属性设置为null。完全没有理由将任何下一个属性设置为null。如果有的话，它会破坏链表。

在第二个if块中，nextNode的next属性设置为nextNode（参见上一点，它表明这个.kNode是nextNode的同义词）。现在您有了一个自引用节点，这是您永远都不想拥有的。此代码使第一个k 1节点自引用，从而有效地将它们从原始链接列表中分离出来。

初始调用是以head Node作为第二个参数进行的。这个变量显然是您所在类的私有成员。但是，在执行反转后，head Node仍然会引用它在调用之前引用的节点。这个名称表明它应该指向列表中的第一个节点，但由于反转会移动前面的另一个节点，因此HeadNode会在完成后指向错误的节点。没有其他变量或属性将指向列表中的第一个节点后，逆转。this. kNode可能是它，但语句this. kNode.next=null和nextNode.next=this. kNode不是你会做的事情列表的第一个节点。

此代码有太多问题，无法清楚地了解您实际尝试做什么。

我建议使用此算法，通过示例进行解释：

list = 1 2 3 4 5 6 7 8
k = 4

将原始第一个节点之后的节点移动到列表的头部

list = 2 1 3 4 5 6 7 8 
k = 3

将原始第一个节点之后的节点移动到列表的头部

list = 3 2 1 4 5 6 7 8 
k = 2

将原始第一个节点之后的节点移动到列表的头部

list = 4 3 2 1 5 6 7 8 
k = 1

当k=1时，无需再移动。

以下是您的代码的外观：

public void reverseListRecursion(int k) {
    // The reversal returns the node that took the first position
    this.headNode = this.reverseNode(this.headNode, k, this.headNode);
};

public Node reverseNode(Node origFirstNode, int k, Node currFirstNode) {
    // If 1 element needs to be reversed, there is nothing to do:
    if (k <= 1) return currFirstNode;

    // Move the node after the original first node before the current first node
    Node movingNode = origFirstNode.next;
    origFirstNode.next = movingNode.next;
    movingNode.next = currFirstNode;

    // The moved node is now the current first node. Repeat:
    return this.reverseNode(origFirstNode, k-1, movingNode);
};

这个解决方案的好处在于，reverseNode方法不需要引用这个。headNode，因此它也可以用于反转列表中间的元素。可以添加将节点作为第二个参数的方法：

public void reverseListRecursionAfter(int k, Node afterNode) {
    afterNode.next = this.reverseNode(afterNode.next, k, afterNode.next);
};

这将反转给定节点之后的节点。

下面是一个实时片段，将相同的代码翻译为JavaScript（仅用于演示）：

// Node class
function Node(val, next) {
    this.val = val;
    this.next = next;
    this.toString = function (cascade) {
        if (!cascade || this.next === null) return '(' + this.val + ')';
        if (this.next === this) return '(' + this.val + ')-loop';
        return '(' + this.val + ')->' + this.next.toString(true); 
    }
}

// List class
function List() {
    this.headNode = null;
    
    this.reverseListRecursion = function(k) {
        // The reversal returns the node that took the first position
        this.headNode = this.reverseNode(this.headNode, k, this.headNode);
    };

    this.reverseNode = function(origFirstNode, k, currFirstNode) {
        // If 1 element needs to be reversed, there is nothing to do:
        if (k <= 1) return currFirstNode;

        // Move the node after the original first node before the current first node
        var movingNode = origFirstNode.next;
        origFirstNode.next = movingNode.next;
        movingNode.next = currFirstNode;
        // The moved node is now the current first node. Repeat:
        return this.reverseNode(origFirstNode, k-1, movingNode);
    };

    this.insert = function (arr) {
        for (var i = arr.length - 1; i >= 0; i--) {
            this.headNode = new Node(arr[i], this.headNode);
        }
    }
        
    this.toString = function () {
        return '{' + this.headNode.toString(true) + '}';
    }
}

var output = [];

// Sample data
var list = new List();
list.insert([1, 2, 3, 4, 5, 6, 7, 8]);
output.push('before: ' + list);

// Make the reversal call
list.reverseListRecursion(4);
output.push('after: ' + list);

// Show result in snippet
document.write(output.join('<br>'));

Answer 2

您的递归应该是

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