是否可以使用Java中的递归来实现一种算法来查找单链列表的第n个元素 [英] Is it possible to implement an algorithm to find the nth to last element of a singly linked list using recursion in java

问题描述

我知道您可以通过在每次传递链表中的节点时使用计数器来递增来简单地迭代解决此问题；还创建一个arraylist并设置在其中的每个节点上找到的数据.一旦点击了链表的尾部，只需从数组列表中的元素总数中减去第N个项，就可以返回答案.但是，有人将如何使用递归执行此操作?是否可以，如果可以，请显示代码以显示您的天才:).

I know that you can simply solve this question iteratively by using a counter to increment each time you pass a node in linkedlist; also creating an arraylist and setting the data found with each node inside it. Once you hit the tail of the linkedlist, just minus the Nth term from the total number of elements in the arraylist and you will be able to return the answer. However how would someone perform this using recursion? Is it possible and if so please show the code to show your genius :).

注意:我知道您不能在Java中返回两个值(但是在C/C ++中，可以使用指针:])

Note: I know you cannot return two values in Java (but in C/C++, you can play with pointers :])

这是我在网上找到的一个简单问题，但是我添加了递归代码，这对我自己构成了挑战，我发现这对于Java来说是不可能的.

This was a simple question I found online but I added the recursion piece to make it a challenge for myself which I've come to find out that it may be impossible with Java.

推荐答案

好的，我认为这应该可以解决问题.这是在 C ++ 中，但是应该易于转换为 Java .我也没有测试.

Okay, I think think this should do the trick. This is in C++ but it should be easy to translate to Java. I also haven't tested.

Node *NToLastHelper(Node *behind, Node *current, int n) {
  // If n is not yet 0, keep advancing the current node
  // to get it n "ahead" of behind.
  if (n != 0) {
    return NToLastHelper(behind, current->next, n - 1);
  }
  // Since we now know current is n ahead of behind, if it is null
  // the behind must be n from the end.
  if (current->next == nullptr) {
    return behind;
  }
  // Otherwise we need to keep going.
  return NToLastHelper(behind->next, current->next, n);
}

Node *NToLast(Node *node, int n) {
  // Call the helper function from the head node.
  return NToLastHelper(node, node, n);
}

如果要返回最后一个节点的值，则可以将其更改为:

edit: If you want to return the value of the last node, you can just change it to:

int NToLast(Node *node, int n) {
  // Call the helper function from the head node.
  return NToLastHelper(node, node, n)->val;
}

如果node为null，此代码将严重失败.

This code will fail badly if node is null.

这篇关于是否可以使用Java中的递归来实现一种算法来查找单链列表的第n个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！