链表中倒数第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--;
}
查看22道真题和解析
