链表中倒数第k个结点

链表中倒数第k个结点

http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a

自己在使用快慢指针方式实现这道题的时候,写出了一个比较有趣的bug,特此记录一下。
bug版本如下:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if(pListHead == NULL) return NULL;
    if(k <= 0) return NULL;

    ListNode* fast = pListHead;
    ListNode* slow = pListHead;
    while(k-- > 0 && fast)
    {
        fast = fast->next;
    }
    if(k) return NULL; // k大于链表长度
    while(fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

有bug的语句就是第一个while循环:

while(k-- > 0 && fast)
{
    fast = fast->next;
}

当k=1时,while循环会继续执行,然后k=0
再次执行while循环时,虽然while判断失败,但是还是执行了k--语句。k是unsigned int类型的,所以现在k变成了一个很大的正整数,就算是有符号类型的,k也变成了负数,下面if(k) return NULL;还是会执行。这就出现了bug。
修正如下:

while(k > 0 && fast)
{
    fast = fast->next;
    k--;
}
全部评论

相关推荐

06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务