首页 > 代码库 > 链表中倒数第K个节点

链表中倒数第K个节点

问题描述:

找出链表中倒数第K个节点

 

思路分析:

用两个指针,一前一后,保持k个距离,前面的指针移动到末尾,后面的指针就刚好直到第k个节点,

要考虑到k为0,倒数第k个节点不存在的情况。

 

参考代码:

ListNode* FindKthToTail(ListNode * pHead,unsigned int k)
{
    if (NULL == pHead || k == 0)
    {
        return NULL;
    }

    ListNode *pAhead = pHead;

    for (unsigned int i = 0;i < k-1;k++)
    {
        if (pAhead->m_pNext != NULL)
        {
            pAhead = pAhead->m_pNext;
        }
        else
        {
            return NULL;
        }
    }

    ListNode *pBehind = pHead;
    while(pAhead->m_pNext != NULL)
    {
        pAhead = pAhead->m_pNext;
        pBehind = pBehind->m_pNext;
    }

    return pBehind;
}

链表中倒数第K个节点