剑指Offer面试题：12.链表的倒数第K个结点

template <typename T>
struct Node
{
public:
    T data;
    Node *pNext;
};

template <typename T>
class ListEx
{
private:
    Node<T> *m_pHead;
    Node<T> *m_pTail;
public:
    ListEx()
    {
        m_pTail = m_pHead = NULL;
    }
    ~ListEx()
    {
        Node<T> *pTemp = NULL;
        Node<T> *pNode = m_pHead;
        while (pNode)
        {
            pTemp = pNode;
            pNode = pNode->pNext;
            delete pTemp;
        }

        m_pHead = m_pTail = NULL;
    }
    void add(T data)
    {
        Node<T> *pNode = new Node<T>;
        pNode->data = data;
        pNode->pNext = NULL;

        if (m_pHead == NULL)
        {
            m_pTail = m_pHead = pNode;
        }

        Node<T>* pTemp = m_pTail;
        pTemp->pNext = pNode;
        m_pTail = pNode;
    }

    Node<T> *GetListHead()
    {
        return m_pHead;
    }
};

// 链表的倒数第k个结点，注意倒数从1开始
template <typename T>
Node<T>* FindKthToTail(Node<T> *pNode, int k)
{
    // k必须不大于Node的结点数目
    if (!pNode || k < 0) return NULL;
    Node<T> *p1 = pNode;
    Node<T> *p2 = pNode;

    int nIndex = 0;
    bool bStart = false;
    int nFalg = 0;
    while (NULL != p2->pNext)
    {
        if (nIndex == k-1)
        {
            bStart = true;
        }
        if (bStart)
        {
            p1 = p1->pNext;
        }

        p2 = p2->pNext;
        nIndex ++;
    }
    return p1;
}

void main()
{
    ListEx<int> *pList= new ListEx<int>();
    pList->add(1);
    pList->add(2);
    pList->add(3);
    pList->add(4);
    pList->add(5);
    pList->add(6);
    pList->add(7);

    Node<int> *pHead = pList->GetListHead();
    Node<int> *pNode = FindKthToTail(pHead, 2);
    cout << pNode->data <<endl;
    pNode = FindKthToTail(pHead, 1);
    cout << pNode->data <<endl;
    pNode = FindKthToTail(pHead, 7);
    cout << pNode->data <<endl;

    delete pList;
}