-1

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

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

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

4

4 回答 4

2

诀窍是在递归之后完成工作。私有方法中的数组基本上用作对可变整数的引用。

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;  
  }
}
于 2013-04-28T03:06:04.220 回答
1

作为一般规则，任何可以用循环完成的事情也可以用任何合理的语言用递归来完成。解决方案的优雅可能大相径庭。这是一个相当 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);
    }
}
于 2013-04-28T02:41:35.377 回答
0

递归函数：

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: %d\n", 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: %d\n", nth->val);
}

此代码已使用不同的输入进行了测试。虽然它是 C++ 版本，但你应该能够弄清楚其中的逻辑 :)

于 2013-08-10T22:06:26.730 回答
0

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

This code will fail badly if node is null.

于 2013-04-28T01:04:00.470 回答