链表中倒数第k个节点

题目：输入一个链表，输出该链表中倒数第么k个节点。为了符合大多数人的习惯，本题从 1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

为了实现只遍历链表一次就能找到倒数第 k 个节点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走 k-1 步，第二个指针保持不动；从第 k 步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在 k-1，当第一个（走在前面的）指针到达链表的尾节点时，第二个（走在后面的）指针正好指向倒数第 k 个节点。

struct ListNode {
    int m_nValue;
    ListNode* m_pNext;
};

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
    // 输入的 pListHead 为空指针
    // 输入的参数k为0
    if(pListHead == nullptr || k == 0)
        return nullptr;
    
    ListNode *pAhead = pListHead;
    ListNode *pBehind = nullptr;
    
    for(unsigned int i = 0; i < k - 1; ++ i)
    {
        if(pAhead->m_pNext != nullptr)
            pAhead = pAhead->m_pNext;
        else
        {
            return nullptr; // 链表的节点数少于k
        }
    }
    
    pBehind = pListHead;
    while(pAhead->m_pNext != nullptr)
    {
        pAhead = pAhead->m_pNext;
        pBehind = pBehind->m_pNext;
    }
    
    return pBehind;
}

摘抄资料：《剑指offer》