链表中倒数第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--;
}
全部评论

相关推荐

到我怀里来:教育背景不用写主修课程,还有你写班级排名是什么意思?咋不写寝室排名呢😂要写就写年纪排名。得了那么多奖结果项目经历什么技术细节都不写清楚,把技术细节写清楚,用了什么技术解决了什么问题,“用了python语言、用了SQL语言”,有这样写的?hr一看就知道你是包装的或者比赛的奖是混的,你什么技术细节都不懂。校内职务全删了,什么三好学生、文明寝室这些你写上去干嘛?重复的奖学金你写三次干嘛?自我评价写那么多干嘛?谁想看这些
点赞 评论 收藏
分享
点赞 评论 收藏
分享
投递顺丰集团等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务