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

public ListNode GetKthFromEnd(ListNode head, int k)
{
    if (head == null) return null;
    var begin = head;
    var end = head;
    for (var i = 0; i < k; i++)
    {
        if (end == null) return null;
        end = end.next;
    }
    while (end != null)
    {
        begin = begin.next;
        end = end.next;
    }
    return begin;
}

為了實(shí)現(xiàn)只遍歷鏈表一次就能找到倒數(shù)第 k 個(gè)結(jié)點(diǎn)，我們可以定義兩個(gè)指針。第一個(gè)指針從鏈表的頭指針開(kāi)始遍歷向前走k-1，第二個(gè)指針保持不動(dòng)；從第 k 步開(kāi)始，第二個(gè)指針也開(kāi)始從鏈表的頭指針開(kāi)始遍歷。由于兩個(gè)指針的距離保持在k-1，當(dāng)?shù)谝粋€(gè)（走在前面的）指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針（走在后面的）指針正好是倒數(shù)第k個(gè)結(jié)點(diǎn)。