1

【インタビューの質問】

単方向にリンクされた整数のリストの末尾 (または末尾) から 5 番目の要素を 1 回のパスで返す関数を作成し、その関数に対する一連のテスト ケースを提供します。

質問に似ています:単方向リストの最後からn番目の要素を見つける方法は? 、しかし、リンクされたリストを一度だけトラバースする必要があるという追加の要件があります。

これが私の解決策です：

struct Lnode  
{
    int val;
    Lnode* next;
    Lnode(int val, Lnode* next=NULL) : val(val), next(next) {}
};


Lnode* kthFromTail(Lnode* start, int k)
{
   static int count =0;
   if(!start)
        return NULL;

   Lnode* end = kthFromTail(start->next, k);
   if(count==k) end = start;
   count++;
   return end;
}

リンクされたリストを 1 回だけトラバースし、暗黙的な再帰スタックを使用しています。もう1つの方法は、2つのポインターを持つことです。高速と低速であり、高速のものは低速のものよりもkポインター高速です.どちらが良いと思われますか? 2 つのポインターを使用したソリューションは、たとえば奇数長のリスト、偶数長のリスト、k > リストの長さなど、多くのケースで複雑になると思います。

4

2 に答える 2

5

2 ポインター ソリューションは、リストを 2 回トラバースするため、要件に適合しません。

あなたのものはより多くのメモリを使用します-正確にはO(n)。リスト内のアイテムの数に等しい再帰スタックを作成していますが、これは理想とはほど遠いものです。

最後のアイテムから k 番目を見つけるには...

より良い（シングルトラバーサル）ソリューション -循環バッファ：

O(k) 余分なメモリを使用します。

長さ k の配列を持つ。

要素ごとに、配列の次の位置に挿入します (ラップアラウンドあり)。

最後に、配列内の次の位置にあるアイテムを返すだけです。

2 ポイント ソリューション:

リストを 2 回トラバースしますが、O(1) の余分なメモリしか使用しません。

最初にp 1と p 2を開始します。

pを1 k 回インクリメントします。

一方、p 1
は      インクリメント p 1および p 2の最後ではありません

p 2は、最後の要素から k 番目を指します。

于 2013-03-02T20:36:37.733 に答える
0 
'n' is user provided value. eg, 5 from last.

int gap=0 , len=0;
myNode *tempNode;

while (currNode is not NULL)
{
 currNode = currNode->next;
 gap = gap+1; 
 if(gap>=n)
   tempNode = currNode;
}
return tempNode;
于 2013-03-03T04:34:02.437 に答える