反转链接列表的第一个K个节点，为什么递归执行两次最后一次迭代 [英] Reversing first K nodes of Linked List,Why recursion executing twice for last iteration

问题描述

在解决链接列表的第一个K个元素的问题时，我已经编写了下面的递归代码，但最后一次迭代执行两次，即k = 1，函数调用reverseNode（）发生两次。任何身体为什么会这样发生。如果我有任何错误，请更正我。

 示例：
 
如果输入是
 
 1  - > 2  - > 3  - > 4→> 5  - > 6  - > 7→> 8 
 
和k = 4，那么输出是
 
 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（\\\
）; 
 this.display（this.headNode）; 
} 
 
 / * 
 *条件K <=链表长度。 
 * / 
 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; //保存K的下一个节点
 this.headNode = nextNode; //将K节点设置为头节点
} 
 if（node == null）{
 nextNode.next = this.kNode; 
} else 
 nextNode.next = node; 
} 
  

解决方案

您的递归应该是

  if（k> 0）{//而不是
k = k-1; 
 this.reverseNode（node，nextNode.next，k）; 
} 
 ... 
  

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

解决方案

Your recursion should be

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

这篇关于反转链接列表的第一个K个节点，为什么递归执行两次最后一次迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！