[牛客]链表中倒数第k个结点
使用快慢指针法:
两种思路:
1.fast先向后走k-1次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点时,slow刚好在倒数第k个位置上;
2.fast先向后走k次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点的后面时(此时为NULL),slow刚好在倒数第k个位置上;
根据这个思路,我们可以写出初始代码如下:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
struct ListNode* fast,*slow;
fast = slow = pListHead;
while(k--)//循环k次
{
fast = fast->next;//fast向后走k次
}
while(fast)//当fast为空时,slow指向倒数第k个结点
{
slow = slow->next;//不为空,同时向后走
fast = fast->next;
}
return slow;
}需要注意代码中while(k--)是循环k次,而while(--k)是循环k-1次.
这样看,代码似乎没什么问题,但是运行之后报了错:
这时我们需要通过测试用例来进行分析
通过第三个用例,我们可以考虑到链表为空的情况
通过第四个用例,考虑到k多于链表结点数时的情况
进行逻辑分析和修改后的代码如下:
正确代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
if(pListHead == NULL)//链表为空
{
return NULL;
}
struct ListNode* fast,*slow;
fast = slow = pListHead;
while(k--)
{
if(fast== NULL)//当k>链表结点数时
{
return NULL;
}
fast = fast->next;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}需要注意的是代码中的if(fast == NULL)语句必须放在fast = fast->next;之前,原因可自行分析
结语：
这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。
希望以上内容对大家有所帮助👀，如有不足望指出🙏**
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-03-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录