[牛客]链表中倒数第k个结点
创始人
2024-06-01 18:42:49
0

使用快慢指针法:

两种思路:

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;之前,原因可自行分析


结语:

这里本章内容就介绍完了,文章中某些内容我们之前有介绍,所以只是一笔带过,还请谅解。

希望以上内容对大家有所帮助👀,如有不足望指出🙏**

前路漫漫!努力变强💪💪 吧!!


相关内容

热门资讯

安卓se系统怎么启用,确保应用... 你有没有发现,你的安卓手机最近有点儿“懒”呢?运行速度慢,反应迟钝,是不是想给它来个“大变身”呢?别...
微软怎么使用安卓系统,技术融合... 你有没有想过,那个以Windows系统著称的微软,竟然也会和安卓系统玩起“亲密接触”?没错,就是那个...
安卓系统耗电特别快,快速诊断与... 手机电量总是不够用?安卓系统耗电特别快,是不是你也遇到了这样的烦恼?别急,今天就来跟你聊聊这个话题,...
安卓机 桌面 系统菜单,功能解... 你有没有发现,你的安卓手机桌面系统菜单,其实就像一个隐藏的宝藏库呢?里面藏着各种各样的功能,等着你去...
安卓ios系统怎么安装,安卓与... 你有没有想过,你的手机里那些好玩的应用是怎么来的呢?是不是觉得安装个软件就像变魔术一样简单?其实,这...
珍奥助手安卓系统下载,轻松体验 你有没有听说最近有个超级好用的助手软件——珍奥助手?没错,就是那个能让你手机生活变得更加便捷的小帮手...
安卓换ios系统.数据,数据迁... 你有没有想过,手机系统就像是我们生活中的衣服,有时候换一件新衣服,整个人都焕然一新呢?没错,今天咱们...
安卓系统提示怎么关,轻松关闭功... 手机屏幕上突然弹出一个安卓系统的提示,让你不禁皱起了眉头。别急,别慌,今天就来手把手教你如何轻松关闭...
安卓系统如何刷回flyme系统... 你是不是也和我一样,对安卓手机的Flyme系统情有独钟呢?有时候,因为一些原因,我们可能需要将手机刷...
手机订餐系统源码安卓,基于手机... 你有没有想过,每天忙碌的生活中,点外卖已经成为了一种不可或缺的享受?而这一切的背后,离不开那些默默无...
顾问营销系统安卓版,助力企业高... 你有没有想过,在这个信息爆炸的时代,如何让你的产品在众多竞争者中脱颖而出呢?别急,今天我要给你介绍一...
安卓系统连接雅马哈音箱,打造个... 你有没有想过,家里的安卓手机和雅马哈音箱也能来个甜蜜的“牵手”呢?没错,今天就要来给你揭秘,如何让这...
安卓系统文件日志查看,揭秘系统... 手机里的安卓系统文件日志,听起来是不是有点儿高深莫测?别担心,今天我就要带你一探究竟,揭开这些神秘日...
努比亚升级安卓p系统,畅享智能... 你知道吗?最近手机界可是热闹非凡呢!努比亚这个品牌,竟然悄悄地给他们的手机升级了安卓P系统。这可不是...
仿苹果装安卓系统,揭秘仿苹果装... 你有没有想过,如果你的苹果手机突然变成了安卓系统,那会是怎样的场景呢?想象你那熟悉的iOS界面,突然...
安装安卓13子系统,全新功能与... 你听说了吗?安卓13子系统终于来了!这可是安卓系统的一大革新,让我们的手机体验更加丰富多元。今天,就...
安卓系统内核日志保存,深度洞察... 你有没有想过,当你手机里的安卓系统在默默运行时,它其实就像一个勤劳的小蜜蜂,不停地记录着它的“工作日...
安卓系统可以调用dll,安卓系... 你知道吗?安卓系统竟然能调用DLL文件,这可是个让人眼前一亮的小秘密呢!想象你手中的安卓设备,不仅能...
安卓通讯 录系统代码,基于安卓... 你有没有想过,你的手机里那个默默无闻的通讯录系统,其实背后有着一套复杂的代码在支撑呢?今天,就让我带...
安卓系统版本对应关系,安卓系统... 你有没有发现,每次手机更新系统,那感觉就像给手机换了个新衣裳,焕然一新呢!不过,你知道吗?安卓系统的...