15.チェーンテーブルの最後からk番目のノード「剣指Offer」(java版)

github
タイトルの説明
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
解決策
1.スタック/再帰
一方向チェーンテーブル使用スタックは、後方から前方への入力を良好に実現することができる.しかし、チェーンテーブルが大きすぎると、再帰的な空間が爆発する可能性があり、スタックもO(n)の空間を使用するので、推奨されないが、これは小さな機能にすぎない.
2 . 二重ポインタの相対変位.
高校の時に学んだ相対変位は、この時に使えます.ターゲットの最後からk番目のとき、あなたはもう1つのポインタが最後のビットを指しているので、彼ら2人の相対的な変位はk-1で、問題は簡単になります.私たちはまず1つのポインタを使って、k-1番目のノードを指して、それから1つのターゲットポインタで最初のノードを指して、それから同時に後ろに歩いて、ポインタが重点に着いたら、後ろのターゲットポインタはちょうど逆数k番目を指している.

/**
 *       ，         k   。
 */
public class _015_FindKthToTail {
    //      
    // 1.       ，                   ，        ，    。
    //         ，       

    //     
    // 2.  ，   ,        ：      ，        ，               .

    /**
     * 3.      
     *     ，        ，        ，
     *             ，            
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        //       
        if (head == null || k <= 0) {
            return null;
        }
        //    ListNode.length() < k,   
        int countK = k;
        ListNode lastNode = head;
        while (countK-- != 1 && lastNode != null) {
            //         k - 1,
            lastNode = lastNode.next;
        }
        if (lastNode == null) {
            //        k   
            return null;
        }
        ListNode targetNode = head;
        while (lastNode.next != null) {
            //         k - 1,
            lastNode = lastNode.next;
            targetNode = targetNode.next;
        }
        return targetNode;
    }
}