是否有可能在java中使用递归实现一种算法来查找单链表的第n到最后一个元素?

Question

我知道你可以简单地通过使用计数器来迭代地解决这个问题，每次你在linkedlist中传递一个节点时都增加;还创建了一个数组列表，并设置其中每个节点的数据。一旦你碰到链表的尾部，只要从数组列表的元素总数中减去第n项，你就能返回答案了。然而，如何使用递归来执行此操作呢?这是可能的，如果是的话，请显示代码来显示你的天才:)。

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

编辑:这是我在网上找到的一个简单的问题，但我添加了递归部分，使其对我自己构成挑战，我发现这可能是Java不可能的。

Answer 1

诀窍是在递归之后进行工作。private方法中的数组基本上用作对可变整数的引用。

class Node {
  Node next;
  int data;
  public Node findNthFromLast(int n) {
    return findNthFromLast(new int[] {n});
  }
  private Node findNthFromLast(int[] r) {
    Node result = next == null ? null : next.findNthFromLast(r);
    return r[0]-- == 0 ? this : result;  
  }
}

Answer 2

作为一般规则，在任何合理的语言中，可以用循环完成的任何事情也可以用递归完成。解决方案的优雅程度可能大不相同。这是一个相当符合java习惯的版本。为简洁起见，我省略了常用的访问器函数。

这里的想法是递归到列表的末尾，并在递归展开时增加计数器。当计数器达到所需值时，返回该节点。否则返回null。非空值会一直返回到顶部。一次向下，一次向上。最小的参数。没有不尊重亚当的意思，但我认为这是相当简单的。

注意:OP关于Java只能返回一个值的声明是正确的，但是由于该值可以是任何对象，因此您可以根据自己的选择返回带有字段或数组元素的对象。但是这里不需要。

public class Test {
    public void run() {
        Node node = null;
        // Build a list of 10 nodes.  The last is #1
        for (int i = 1; i <= 10; i++) {
            node = new Node(i, node);
        }
        // Print from 1st last to 10th last.
        for (int i = 1; i <= 10; i++) {
            System.out.println(i + "th last node=" + node.nThFromLast(i).data);
        }
    }
    public static void main(String[] args) {
        new Test().run();
    }
}
class Node {
    int data;   // Node data
    Node next;  // Next node or null if this is last
    Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    // A context for finding nth last list element. 
    private static class NthLastFinder {
        int n, fromLast = 1;
        NthLastFinder(int n) {
            this.n = n;
        }
        Node find(Node node) {
            if (node.next != null) { 
                Node rtn = find(node.next);
                if (rtn != null) {
                    return rtn;
                }
                fromLast++;
            }
            return fromLast == n ? node : null;
        }
    }
    Node nThFromLast(int n) {
        return new NthLastFinder(n).find(this);
    }
}

Answer 3

好吧，我想我想这应该能成功。这是在C++中，但它应该很容易转化为Java。我也没有测试。

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:如果要返回最后一个节点的值，只需将其更改为:

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

Answer 4

递归函数:

int n_to_end(Node *no, int n, Node **res)
{
    if(no->next == NULL)
    {
            if(n==0)
                    *res = no;
            return 0;
    }
    else
    {
            int tmp = 1 + n_to_end(no->next, n, res);
            if(tmp == n)
                    *res = no;
            return tmp;
    }
}

包装器函数:

Node *n_end(Node *no, int n)
{
    Node *res;
    res = NULL;
    int m = n_to_end(no, n, &res);
    if(m < n)
    {
            printf("max possible n should be smaller than or equal to: %dn", m);
    }
    return res;
}

调用函数:

int main()
{
    List list;
    list.append(3);
    list.append(5);
    list.append(2);
    list.append(2);
    list.append(1);
    list.append(1);
    list.append(2);
    list.append(2);
    Node * nth = n_end(list.head, 6);
    if(nth!=NULL)
    printf("value is: %dn", nth->val);
}

这段代码已经用不同的输入进行了测试。虽然这是一个c++版本，你应该能够找出逻辑:)