java - リンクリスト3要素について

Question

私はデータ構造の世界の初心者であり、それを学んでいます。リンクリストに関する質問があります。インタビューの1つで、リンクリストのコンテキストで尋ねられたのはリンクリストの最後から3番目の要素を見つける方法です。 1回のパスでリストします。これについてはわかりません。アドバイスしてください。

Answer 1

if(node.next.next.next == null)

少し汚いですが、基本的には、さらに下のノード3ノードがnullかどうかを確認します。もしそうなら、あなたは最後から3番目のものを持っています。もちろん、これは3未満のサイズのリストを考慮していません。

Answer 2

私が想定しているリストの最初のノードはheadと呼ばれます。

したがって、ポインタをヘッドに設定します。これを現在と呼びます

Node current = head;

次に、3つ先を指す別のポインターを作成します

Node threeAhead = head.next.next.next;

次に、threeAhead.nextがnullであるかどうかを最初にチェックするループを記述します。そうでない場合は、次のようにします。

threeAhead = threeAhead.next;
curr = curr.next;

threeAhead.nextがnullになると、現在の最後から3つの位置になります。

Answer 3

開始する前にリストの長さがわかっている場合は、JBNizetのアプローチを使用してください

node = first;
for (i = 0; i < length - N_FROM_END; i++) {
    node = node.next;
}

result = node.value

あなたが今長さを知らないならば：

nodes = new Node[N_FROM_END];
node = first;
for (i = 0; node != null; i++) {
    nodes[i % N_FROM_END] = node;
    node = node.next;
}
result = nodes[i % N_FROM_END].value

またはそのようなもの。（境界条件を確認してください...そしてリストの長さが未満であることを考慮してくださいN_FROM_END。）

どちらの回答も、「最大で1回ノードにアクセスする」という制約を満たしています。