問題
輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個節(jié)點，鏈表的倒數(shù)第0個節(jié)點為鏈表的尾指針。

解答
設(shè)置兩個指針 fast、slow，首先 fast 和 slow 都指向 head，然后 fast 向前走 k 步，這樣 fast 和 slow 之間就間隔 k 個節(jié)點，最后 fast 和 slow 同時向前移動，直至 fast 走到鏈表末尾, 這是slow指向的就是第k個節(jié)點。

代碼如下：

Node* theKthNode(Node *head,int k)
{
    if(k < 0) return NULL;    //異常判斷
    Node *slow,*fast;
    slow = fast = head;
    int i = k;
    for(;i>0 && fast!=NULL;i--)
    {
        fast = fast->next;
    }
    if(i > 0)    return NULL;    //考慮k大于鏈表長度的case
    while(fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

注意該題中使用了雙指針來遍歷鏈表，雙指針策略可以解決很多經(jīng)典的關(guān)于鏈表的問題，如鏈表是否有環(huán)。

經(jīng)典面試100題 - 持續(xù)更新中