PHP面接問題ベスト1——チェーンテーブルの最後からK番目のノード

単一のチェーンテーブルを入力し、チェーンテーブルの最後のK番目のノードを出力します.最後の1番目のノードはチェーンテーブルの最後のノードです.チェーンテーブルのノードは次のように定義されます.

class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}

構想1:このチェーンテーブルにn個のノードがあると仮定すると,最後からk番目のノードは,最初からn−k−1番目のノードである.従って、まずチェーンテーブルを1回遍歴し、チェーンテーブルの長さnを取得した後、チェーンテーブルをn−k−1番目のノードに最初から遍歴し、出力することができる.
構想2:スタックの後入先出の原則を利用して、補助スタックを創立して、チェーンテーブルを遍歴して、そしてノードを順次スタックに入れて、それからスタックのk番目のノードを出ればいいです.
考え方3:2つのポインタP 1を設定し、P 2はチェーンテーブルのヘッダノードを指し、チェーンテーブルを遍歴し、ポインタP 1はまずk-1個のノードを前方に移動し、その後P 1,P 2は同時に前方に移動し、P 1がチェーンテーブルの終端ノードに達したとき、P 2が指すのは最後からk番目のノードである.
構想三の実現コード:

function FindKthToTail($head, $k)
{
    if($head == NULL || $k <= 0)
        return NULL;
    
    $retNode = NULL;
    $pNode = $head;
    $i = 1;
    while($pNode)
    {
        if($i == $k) {
            // pNode   K-1  ， retNode     
            $retNode = $head;
        }
        else if($i > $k) {
            $retNode = $retNode->next;
        }
        
        $pNode = $pNode->next;
        $i++;
    }
    
    return $retNode;
}