ByteDance アルゴリズムの面接の質問、解けますか?

数日前、私の友人がByteDanceの面接を受けました。面接官は彼にリンクリストアルゴリズムの質問をしましたが、彼はすぐには理解できなかったので私に尋ねました。この質問はかなりいいと思うので、それについて話します。

[[275586]]

01 タイトル

これは実際には変形されたリンクリストの反転問題であり、大まかに次のように説明できます。

単一リンクリストのヘッドノードが与えられた場合、リストを調整して K 個のノードすべてが逆順にグループ化されるようにする関数を実装します。リンクリストの末尾から始めて、ヘッドに残っているノードの数がグループを形成するのに十分でない場合は、順序を逆にする必要はありません。 (キューやスタックを補助として使用することはできません)。

例えば：

リンクリスト: 1->2->3->4->5->6->7->8->null、K = 3。すると、6->7->8、3->4->5、1->2 はそれぞれグループになります。調整後：1->2->5->4->3->8->7->6->null。このうち、1と2は1グループに足りないため調整しません。

02 回答

この問題の難しさは、リンクリストの先頭からではなく末尾から開始することです。先頭であれば、リンクリストをトラバースして、k 回のトラバースごとにグループに分割し、順序を逆にすることができるため、比較的簡単に実行できます。しかし、これは最後とは異なります。なぜなら、これは単方向リンクリストであり、逆方向にトラバースして最初からやり直すことができないからです。ただし、この問題は再帰を使用すると間違いなく簡単に解決できます。

まずは同じような逆の質問をしてみましょう。

この問題を解く前に、先頭から始める場合に何をすべきかを見てみましょう。例: リンクリスト: 1->2->3->4->5->6->7->8->null、K = 3。調整後：3->2->1->6->5->4->7->8->null。このうち、7と8は1グループに足りないため調整されません。

この問題を解決するには再帰を使用することができます。reverseKNode() メソッドの機能は、単方向リンクリスト内の K 個のノードの順序を (先頭から) 逆にすることであると仮定します。reverse() メソッドの機能は、単方向リンクリストを逆にすることです。

したがって、次の単一リンクリストの場合、K = 3 になります。

最初の K 個のノードを次のノードから分離します。

temp が指す残りのリンクリストは、元の問題のサブ問題であると言えます。 temp が指すリンクリスト内の K 個のノードすべての順序を逆にするには、reverseKNode() メソッドを呼び出します。次に、reverse() メソッドを呼び出して、head が指す 3 つのノードの順序を逆にします。結果は次のようになります。

次に、これら 2 つの部分を接続するだけです。最終結果は次のとおりです。

コードは次のとおりです。

話題に戻る

これら 2 つの質問は、1 つは最初から始まり、もう 1 つは最初から始まるという点を除けば、非常によく似ていると言えます。これは、leetcode の質問 25 でもあります。面接では、質問が歪んでいることがよくあります。たとえば、ByteDance からのこの質問では、質問が最後から組み立てられており、一瞬何をすればいいのかわからないかもしれません。もちろん、誰かがすぐに反応して彼を即座に殺す可能性もあります。

実際、この問題は非常に簡単に解決できます。単方向リンクリストを 1 回反転するだけです。反転後、先頭からアセンブルするように変換できます。次に、上記の私の解決策に従ってください。処理後、結果をもう一度反転すると完了します。 2 度反転すると反転しないのと同じになります。

例えばリンクリスト（K = 3）の場合

最後から始めて、逆の順序で K 個のノードをグループ化します。手順は次のとおりです。

①まずは逆順

順序を逆にした後、先頭から始めて各 K ノードの順序をグループとして逆にするという問題に変換できます。

②処理後の結果は以下のようになります。

③ 次に結果を1回反転すると、結果は次のようになります。

コードは次のとおりです。

この問題と同様に、まず 2 つのリンクリストを逆の順序で追加する必要があります。この質問は、ByteDance の筆記試験でも出題されており、下の図の 2 番目の質問に示されています。

この問題では、まず 2 つのリンクリストを逆にし、次にノードを追加し、最後にそれらをマージする必要があります。