首页 > 代码库 > 链表中倒数第k个结点

链表中倒数第k个结点

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

链表的定义如下:

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

常规思路:遍历链表两次,第一次统计出链表结点的个数,第二次就能找到倒数第k个结点。

        但是有方法使我们只需要遍历依次链表就可以。如之前的那样,我们可以设置两个指针。第一个指针从链表的头开始遍历向前走k-1,第二个指针保持不动。从第k步开始,第二个指针也从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当走在前面的指针达到链表的尾部时,后面的指针正好指向倒数第k个节点。

        我们还需要考虑程序的鲁棒性的问题:1.如果输入的是空指针,程序会崩溃2.如果链表的结点总数少于k,则我们将试图访问空指针而程序崩溃。3. 输入的k为0,则k-1将会是0xFFFFFFFF,因此循环的执行次数将远远超过我们的预期,同样会使程序崩溃。

        基于此分析,实现代码如下:

ListNode* FindKthToTail(ListNode* pListHead,unsigned int k)
{
    if(pListHead==NULL||k==0)
        return NULL;
    
    ListNode *pAhead=pListHead;
    ListNode *pBehind=NULL;
    
    for(unsigned int i=0;i<k-1;i++)
    {
        if(pAhead->m_pNext!=NULL)
            pAhead=pAhead->m_pNext;
        else
        {
            return NULL;
        }
    }
    
    pBehind=pListHead;
    while(p-Ahead->m_pNext!=NULL)
    {
        pAhead=pAhead->m_pNext;
        pBehind=pBehind->m_pNext;
    }
    
    return pBehind;
}

扩展:当我们用一个指针遍历链表不能解决问题的时候,可以尝试用两个指针来遍历链表。可以让一个指针遍历的速度快一些,比如一次在链表上走两步,或者让它先在链表上走若干步。可以解决的类似问题:求链表的中间节点;判断一个单向链表是否形成了环形结构等等问题。


本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1583108

链表中倒数第k个结点