JavaScript版「剣指offer」ブラシ問題(13)チェーンの最後からk番目の結点


1.テーマの説明
チェーンを入力して、このチェーンの最後から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