フロントエンドのよくあるアルゴリズムの面接問題です.最後からチェーンを印刷します.「JavaScript解法」
1697 ワード
フロントエンドのよくあるアルゴリズムの面接問題です.最後からチェーンを印刷します.「JavaScript解法」テーマ記述 構想を実現します. コード実現 テーマの説明
チェーンの頭の結点を入力して、最後の端から逆さまに各結点の値を印刷します.
構想を実現する
フロントエンドエンジニアはこのテーマを見て、直接に思いついたのは、ルーシーループを書いてチェーンテーブルを巡回し、ループの中でノードの値を配列に保存し、最後に配列を倒順にした後、行列を通して各値を印刷します.
この問題がこんなに簡単だったら、面接官は試験を受けません.
面接官が、配列を使用してはいけないと要求したら、どう解決しますか?
チェーンですから、きっと遍歴します.遍歴の順序は最初から最後までですが、出力の順序は最後までです.
つまり先に入手したデータを最後に出力します.最後に入手したデータは、最初の出力です.スタックの定義と似ているような感じがしますか?スタックは「後進先出」です.問題の要求もです.
再帰的本質はスタック構造であるので、再帰的に実現する.毎回継続して、先に後のノードを出力し、現在のノードを出力する.
コードの実装
チェーンの頭の結点を入力して、最後の端から逆さまに各結点の値を印刷します.
構想を実現する
フロントエンドエンジニアはこのテーマを見て、直接に思いついたのは、ルーシーループを書いてチェーンテーブルを巡回し、ループの中でノードの値を配列に保存し、最後に配列を倒順にした後、行列を通して各値を印刷します.
この問題がこんなに簡単だったら、面接官は試験を受けません.
面接官が、配列を使用してはいけないと要求したら、どう解決しますか?
チェーンですから、きっと遍歴します.遍歴の順序は最初から最後までですが、出力の順序は最後までです.
つまり先に入手したデータを最後に出力します.最後に入手したデータは、最初の出力です.スタックの定義と似ているような感じがしますか?スタックは「後進先出」です.問題の要求もです.
再帰的本質はスタック構造であるので、再帰的に実現する.毎回継続して、先に後のノードを出力し、現在のノードを出力する.
コードの実装
function printListFromTailToHead(head) {
if (head.next) {
printListFromTailToHead(head.next);
}
console.log(head.val);
}
コードは爽やかに見えますが、再帰的には問題があります.パラメータが大きいと、循環呼び出しレベルが深くなり、スタックオーバーフローを引き起こす可能性があります.今後どのように最適化するか検討します.