java反转链表的前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;
    }
}

1. wile循环将使递归调用的数量增加到k。也许这是你的意图，但它肯定不会成为一个有效的算法。这项工作可以通过移动k-1节点来完成，因此使k呼叫效率不高

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

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

4. 第一个if块中的代码使this.kNode成为nextNode的同义词，然后将其next属性设置为null。应该没有理由将任何next属性设置为null。如果有的话，它将打破链表

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

6. 初始调用使用头节点作为第二个参数。此变量显然是您所在类的私有成员。但是，在执行反转后，头节点仍将引用调用前它引用的节点。名称表明它应该指向列表中的第一个节点，但由于反转将移动前面的另一个节点，headNode将在完成后指向错误的节点。没有其他变量或属性会指向反转后列表中的第一个节点<这个。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);
};

这个解决方案的好处是，^ {< CD21>}方法不需要引用^ {CD22>}，因此它也可以用于在列表中间反转元素。您可以添加此方法，该方法将节点作为第二个参数：

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

这将反转给定节点后面的节点

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

&13； 第13部分,；

// 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>'));

；

和#13；