單鏈表查找倒數第k個節點

題目描述：單鏈表查找倒數第k個節點

分析：單鏈表是一個單向的鏈式結構，所以不可能從鏈表尾部向前找第k個結點，因此只能想辦法從鏈表的頭部開始找。

假設一個給定一個鏈表，長度為 6，現在查找倒數第 2 個結點：

給定兩個指針， fast 和 slow 開始都讓他們指向頭結點

首先，讓 fast 指針先走到正數第 k 個結點，也就是走 k-1 步，這里 k=2,所以先讓 fast 走1步

這時讓 slow 指針跟著 fast 指針一塊走，直到 fast 指針走到最后一個節點（注意：這里是最后一個節點，而不是空節點），此時 slow 指針所指向的節點就是我們要找的倒數第 k 個結點了

當然，這里只是大致的思想，具體的很多細節問題（比如： k值大于鏈表的長度，k = 0 的情況等等），需要自己處理。

主要代碼如下:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
    {
        if(pListHead == NULL || k == 0) //一些異常情況
        {
            return NULL;
        }
        
        ListNode* fast = pListHead;
        ListNode* slow = pListHead;
        
        while(fast && --k)  //這里一定要先自減，因為兩個指針開始都指向頭結點
        {
            fast = fast->next;
        }
        
        if(fast == NULL)  //即沒找到的情況
        {
            return NULL;
        }
        
        if(k == 0)
        {
            while(fast->next != NULL)
            {
                fast = fast->next;
            	slow = slow ->next;
            }
            
        }

        return slow;
    }