首页 > 技术文章 > 寻找一个单链表的倒数第K个节点

7ants 2013-09-02 22:50 原文

思路:设两个指针pStart,pEnd,二者之间差K个节点,当pEnd到达末尾的时候,pStart刚好指向倒数第K个节点

LinkNode * findKthNode(LinkNode * pHead, int K)
{
    if(pHead == NULL)
        return NULL;
    LinkNode * pStart = 0;
    LinkNode * pEnd = 0;
    int i = 0;
    for (pEnd = pHead, pStart = pHead; pEnd != NULL; pEnd = pEnd->_next)
    {
        if(i < K)
        {
            ++i;
            continue;
        }
        else
            pStart = pStart->_next;
    }
    if (i < K)
        return NULL;
    else
        return pStart;
}
int main()
{
    LinkNode * pHead = 0;
    int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
    for (int i = 0; i<sizeof(a) / sizeof(a[0]); i++)
    {
        createLink(pHead,a[i]);
    }
    printLink(pHead);
    cout<<"倒数第12个节点是"<<findKthNode(pHead,12)->_value<<"\n";
    return 0;
}

 

推荐阅读