5

だから私は試験からこの質問を得ました。

片方向リストの末尾から n 番目のノードを取得するにはどうすればよいでしょうか?

各ノードには、値と次 (次の値へのポインター) があります。これが与えられます：

getNodeFromTail(Node head, int x) {

}

したがって、私が行った方法は、リストを一度トラバースしてリストの長さを見つけることです。次に、(長さ - x) ノードを取得します。したがって、合計で 2 回のトラバーサルです。

getNodeFromTail(Node head, int x) {
    int length = 0;
    Node headdupe = head;
    while (headdupe.next != NULL) {
         headdupe = headdupe.next;
         length++;
    }
    int a = length--;
    for (int y = 0; y < a; y++) {
         head = head.next;
    }
    return head;
}

これは正しいですが、同じことができるかどうかを尋ねるおまけの質問もありますが、1 回だけトラバースします。試験中は思いつかなかったのですが、ある方法を考えた後、あまりよくわかりません。

長さ x の ArrayList を作成できます。その後、while ループを実行するたびに、配列の先頭に要素を追加し、カスケード ダウンして、配列の最後の要素を開始します。次に、ヘッドが null にヒットすると、配列 [x-1] のノードを返します。

これは正しいですか？より良い解決策はありますか？

4

6 に答える 6

3

私は次のことをします：

サイズの循環バッファーを保持しx、リストをトラバースするときにノードを追加します。リストの最後に到達すると、末尾から x 番目のエントリが循環バッファ内の次のエントリと等しくなります。

擬似コード:

Node getNodeFromTail(Node head, int x) {
  // Circular buffer with current index of of iteration.
  int[] buffer = new int[x];
  int i = 0;

  do {
    // Place the current head in its position in the buffer and increment
    // the head and the index, continuing if necessary.
    buffer[i++ % x] = head;
    head = head.next;
  } while (head.next != NULL);

  // If we haven't reached x nodes, return NULL, otherwise the next item in the
  // circular buffer holds the item from x heads ago.
  return (i < x) ? NULL : buffer[++i % x];
}

このソリューションには追加xのメモリが必要であり、ランタイム時間をメモリと交換する典型的な例です。

x注: 入力リストが未定義よりも小さい場合の対処方法。

于 2013-09-23T19:44:33.850 に答える
1

2回のトラバースや再帰なしで実行できます。以下を参照してください。

int getNodeFromTail(Node head, int position)
{
    if (head == NULL)
      return 0;

      // 2 pointers needed
      Node first = head;
      Node sec = head;

      for(int i = 0; i < position; i++)
        sec = sec.next;

      while (sec.next != NULL)
      {
        sec = sec.next;
        first = first.next;
      }

      return first;
}
于 2014-01-08T12:35:17.797 に答える