題目：

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。為了符合大多數(shù)人的習(xí)慣，本題從1開始計(jì)算，即鏈表的尾結(jié)點(diǎn)是倒數(shù)第k個(gè)結(jié)點(diǎn)。例如一個(gè)鏈表有6個(gè)結(jié)點(diǎn)，從頭開始他們的值一次是1、2、3、4、5、6.這個(gè)鏈表的第3個(gè)結(jié)點(diǎn)是值為4的結(jié)點(diǎn)。

思路：

定義兩個(gè)指針pAhead,pBehind。
1）第一個(gè)指針pAhead從鏈表的頭部開始遍歷，先走k-1步。（此時(shí)pAhead位置在鏈表的第k位置，頭指針為第1個(gè)位置）
2）到第k步，第二個(gè)指針pBehind也開始遍歷。此時(shí)兩個(gè)指針的距離保持在k-1.
3）接著，兩指針一起移動(dòng)。當(dāng)?shù)谝粋€(gè)pAhead到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針pBehind剛好在鏈表倒數(shù)第k結(jié)點(diǎn)。

注：難點(diǎn)是搞清楚兩個(gè)指針之間的位置關(guān)系，倒數(shù)第k位置，那么他們距離應(yīng)相隔k-1。
同時(shí)，需考慮輸入的鏈表為空，鏈表沒有k個(gè)結(jié)點(diǎn)的特殊情況。

解答：

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        //特殊情況測(cè)試用例
        solution.FindKthToTail(null, 0);
        //普通測(cè)試用例{1,2,3,4,5}，1略
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode pAhead = head;
        ListNode pBehind = null;

        //前一個(gè)指針先走k-1步
        int times = 1;
        while (times++ < k) {
            if (pAhead.next != null) {
                pAhead = pAhead.next;
            } else {
                return null;
            }
        }

        // 第k步，第二個(gè)指針也從頭開始遍歷鏈表。兩指針距離保持在k-1
        pBehind = head;
        //兩個(gè)指針一起移動(dòng)，當(dāng)前一個(gè)指針到達(dá)尾結(jié)點(diǎn)，后一個(gè)指針正好在倒數(shù)第k個(gè)結(jié)點(diǎn)
        while (pAhead.next != null) {
            pAhead = pAhead.next;
            pBehind = pBehind.next;
        }
        return pBehind;
    }
}