JavaScript版「剣指offer」ブラシ問題(13)チェーンの最後からk番目の結点
1623 ワード
1.テーマの説明
チェーンを入力して、このチェーンの最後からk番目のノードを出力します.
2.考え方
タイトル:チェーンを入力して、このリストの最後からk番目のノードを出力します.要求:大多数の人の習慣に合うために、本題は1から数えます.すなわちチェーンの最後のノードは最後から一番目のノードです.例えば、一つのチェーンは6つのノードがあります.最初のノードから順に、彼らの値は1、2、3、4、5、6となります.このチェーンの最後から3番目のノードは4という値を持つノードです.
共通の考え方:チェーンを通して一つの針で問題を解決できない時、二つのポインタでチェーンを巡ることができます.すべては最初のノードから出発します.その中の一つのポインタが遍歴する速度を速くしてもいいです.例えば、一回に二歩行って、中間ノードを探す時)、あるいはチェーンにいくつかのステップを歩かせてもいいです.
3.コード
まず二つのチェーンを巡る解法を見ます.
リンク長を巡回して取得し、kに基づいてインデックスを決定し、再びチェーンテーブルを巡回します.
//チェーンを通して、2つのポインタを使って、彼らの間の距離の差k-1/尾の針は先にk-1歩行って、k番目のステップに行って、2つのポインタは一緒に歩きます.最後のポインタがチェーンの最後のノードに達すると、頭のポインタの位置は最後からk番目です.
つまり、2つの点の間の距離が固定されています.これにより、尾のポインタが尾のポインタとの距離が固定されているため、頭のポインタが最後のk番目になります.
チェーンを入力して、このチェーンの最後からk番目のノードを出力します.
2.考え方
タイトル:チェーンを入力して、このリストの最後からk番目のノードを出力します.要求:大多数の人の習慣に合うために、本題は1から数えます.すなわちチェーンの最後のノードは最後から一番目のノードです.例えば、一つのチェーンは6つのノードがあります.最初のノードから順に、彼らの値は1、2、3、4、5、6となります.このチェーンの最後から3番目のノードは4という値を持つノードです.
共通の考え方:チェーンを通して一つの針で問題を解決できない時、二つのポインタでチェーンを巡ることができます.すべては最初のノードから出発します.その中の一つのポインタが遍歴する速度を速くしてもいいです.例えば、一回に二歩行って、中間ノードを探す時)、あるいはチェーンにいくつかのステップを歩かせてもいいです.
3.コード
まず二つのチェーンを巡る解法を見ます.
リンク長を巡回して取得し、kに基づいてインデックスを決定し、再びチェーンテーブルを巡回します.
function kNodeInList(head, k) {
if(head === null || k === 0) {
return null;
}
let len = 0;
let tempNode = head;
while(tempNode) {
tempNode = tempNode.next;
++len;
}
if(k > len) {
return null;
}
let index = len - k + 1;
result = head;
for(let i=1; i< index; ++i) {
result = result.next;
}
return result;
}
もう一つの解法を見ます.//チェーンを通して、2つのポインタを使って、彼らの間の距離の差k-1/尾の針は先にk-1歩行って、k番目のステップに行って、2つのポインタは一緒に歩きます.最後のポインタがチェーンの最後のノードに達すると、頭のポインタの位置は最後からk番目です.
つまり、2つの点の間の距離が固定されています.これにより、尾のポインタが尾のポインタとの距離が固定されているため、頭のポインタが最後のk番目になります.
function kNodeInList(head, k) {
if(head === null || k === 0) {
return null;
}
let pHead = tail;
let pTail = tail;
for(let i=0; i
参考記事:https://www.cnblogs.com/echovic/p/6430678.html https://www.cnblogs.com/wuguanglin/p/FindKthToTail.html https://github.com/DavidChen93/-offer-JS-/blob/master/22.1 リストから最後からk番目のノード.js