-1

リンクリストでノードを渡すたびにカウンターを使用してインクリメントすることで、この質問を繰り返し解決できることを私は知っています。また、arraylist を作成し、その中の各ノードで見つかったデータを設定します。リンクリストの末尾に到達すると、arraylist の要素の総数から N 番目の項を差し引くだけで、答えを返すことができます。しかし、誰かが再帰を使用してこれをどのように実行しますか? 可能であれば、あなたの天才を示すコードを表示してください:)。

注: Java では 2 つの値を返すことができないことはわかっています (ただし、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 に答える
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 に答える