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