[牛客]链表中倒数第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;之前,原因可自行分析


结语:

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

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

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


相关内容

热门资讯

安卓系统自动退出应用,原因解析... 手机里的应用突然自动退出,是不是让你头疼不已?别急,让我来给你揭秘安卓系统自动退出应用的那些事儿!一...
安卓模仿苹果11系统,深度模仿... 你有没有想过,如果你的安卓手机也能拥有苹果iOS 11的酷炫界面呢?想象那圆角矩形的应用图标,流畅的...
安卓强制设置系统桌面,功能解析... 亲爱的手机控们,你是否曾为手机桌面乱糟糟而烦恼?或者,你是否想尝试一款全新的桌面,却苦于无法更改系统...
微单底层系统安卓系统,深入解析... 你有没有想过,那些小巧精致的微单相机,它们的“心脏”到底是什么?没错,就是微单的底层系统,而它竟然是...
安卓系统鼠标调整软件,轻松实现... 你是不是也和我一样,在使用安卓手机时,偶尔会遇到鼠标操作不太顺畅的情况?别急,今天就来给你安利几款特...
安卓视频管理系统下载,高效下载... 你有没有想过,家里的安卓设备里视频乱糟糟的,找起来简直像大海捞针?别急,今天就来给你安利一款神器——...
安卓系统坐标定位,基于安卓系统... 探秘安卓系统坐标定位:你的位置,我来揭秘 想象你正走在熙熙攘攘的街头,突然收到一条信息:“你的位置已...
安卓系统怎么传视频,一键操作指... 你有没有想过,手机里的视频怎么才能轻松传到另一台设备上呢?别急,今天就来给你揭秘安卓系统传视频的几种...
安卓原生系统怎么装,具体操作可... 你有没有想过,你的手机系统是不是也能来个“大变身”?没错,就是那个传说中的安卓原生系统!听起来是不是...
一加原声安卓系统,一加3T原生... 你有没有发现,现在手机的世界里,系统就像是每个品牌的灵魂,而一加的原声安卓系统,简直就是一股清流,让...
游戏手机的安卓系统,探寻安卓2... 哎呀呀,你有没有想过,手机也能玩出花来?没错,就是那种专为游戏发烧友量身定制的游戏手机,它们不仅硬件...
bampo耳机支持安卓系统,畅... 你有没有想过,一款耳机不仅能让你沉浸在美妙的音乐世界里,还能让你的生活更加便捷?今天,就让我带你走进...
安卓13系统推送时间,各大品牌... 你知道吗?最近科技圈可是炸开了锅,因为安卓系统的大动作又来了!没错,就是那个我们每天不离手的安卓13...
荣耀平板13安卓系统,畅享高效... 你有没有发现,最近平板电脑界又掀起了一股热潮?没错,就是荣耀平板13,这款搭载了安卓系统的平板,简直...
beats耳机安卓系统如何,连... 你有没有想过,那些在街头巷尾随处可见的时尚Beats耳机,是不是也能在你的安卓手机上大显身手呢?今天...
安卓双系统打号,打造个性化多能... 你有没有想过,你的安卓手机也能变身成超级英雄,拥有双重身份呢?没错,就是安卓双系统!想象一边是熟悉的...
安卓系统最大的优势,开放性与生... 你有没有发现,现在手机圈里最火的操作系统非安卓系统莫属了!它就像一个万能的小超人,不管是什么手机品牌...
安卓系统抄袭了苹果,技术融合下... 最近手机圈可是热闹非凡呢!安卓系统竟然被说成是抄袭了苹果,这可真是让人大跌眼镜。咱们就来聊聊这个话题...
精简好用的安卓系统,精简版安卓... 亲爱的手机控们,你是否曾为手机运行缓慢、存储空间不足而烦恼?别担心,今天我要给你带来一个超级实用的秘...
小米平板改为安卓系统,轻松切换... 你有没有发现,最近小米平板的更新可是越来越有意思了呢!听说,小米平板要改用安卓系统啦!这可真是让人兴...