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


结语:

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

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

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


相关内容

热门资讯

安卓版手机系统下载,畅享智能生... 亲爱的手机控们,你们是不是也和我一样,对安卓版手机系统下载充满了好奇和期待呢?想象你的手机就像是一块...
安卓系统的桌面程序,功能与应用... 亲爱的读者们,你是否曾好奇过,你的手机桌面背后隐藏着怎样的奥秘?今天,就让我带你一起揭开安卓系统桌面...
安卓下载最新系统,修复多项bu... 手机升级大作战:安卓最新系统下载攻略亲爱的手机控们,你是否也和我一样,对手机的新功能充满期待?想要让...
安卓系统如何变成中文,安卓系统... 亲爱的手机控们,你们有没有遇到过这种情况:拿着一款安卓手机,看着那密密麻麻的英文菜单,心里直发怵?别...
安卓手机怎么定制系统,安卓手机... 你有没有想过,你的安卓手机其实可以是个“小变脸”呢?没错,就是那种可以随心所欲改变外观和功能的魔法。...
安卓系统查询使用痕迹,揭秘使用... 手机里的秘密可真多,你有没有想过,你的手机到底都记录了些什么呢?别急,今天就来带你一探究竟,看看安卓...
鸿蒙系统为啥还是安卓,自主研发... 最近是不是被鸿蒙系统刷屏了?华为这个国产操作系统,自从发布以来就备受关注。不过,很多人都在问:鸿蒙系...
荣耀平板下载安卓系统,解锁无限... 你有没有想过,你的荣耀平板电脑是不是也能像智能手机一样,拥有各种酷炫的安卓系统呢?没错,今天就要来给...
怎么解锁安卓系统解,全方位解锁... 手机屏幕上那串熟悉的数字密码,怎么就突然成了我的“心结”了呢?别急,别慌,今天就来给你支几招,让你的...
区分安卓和苹果系统,全面对比与... 你有没有想过,为什么你的手机里装了那么多应用,而别人的手机却看起来那么清爽?这背后,其实隐藏着安卓和...
安卓系统文件特别乱,探寻秩序与... 亲爱的手机,你最近是不是感觉有点儿“胖”了呢?别担心,今天就来给你做个大扫除,让你的安卓系统文件变得...
安卓系统怎样看日历,Andro... 你有没有发现,时间就像那溜走的兔子,总是悄无声息地跑得飞快。想要抓住时间的尾巴,管理好每一天,一款好...
奥迪新车系统安卓版,本土化体验... 哇塞,你知道吗?最近奥迪又放大招了!他们家的新款A4L竟然搭载了安卓系统,这可是奥迪品牌首次引入安卓...
安卓系统秒变电脑,手机变电脑体... 你有没有想过,你的安卓手机竟然能秒变一台电脑?是的,你没听错,就是那种可以装软件、玩游戏的电脑!今天...
苹果有安卓系统版本,苹果iOS... 你有没有想过,苹果手机居然也能用安卓系统的软件?是的,你没听错,这个神奇的跨界现象正在悄悄发生。今天...
xp 系统安卓驱动下载,轻松实... 你那台老式的Windows XP电脑是不是突然成了摆设,因为它怎么也认不出你的安卓手机了呢?别急,今...
安卓双系统切换 nfc,安卓双... 你有没有想过,手机里的安卓双系统切换加上NFC功能,竟然能玩出这么多花样?没错,今天就来给你揭秘这个...
安卓系统连接菲翔,操作指南与技... 你有没有想过,你的安卓手机和菲翔之间也能建立起一种特别的联系呢?没错,就是那种可以让你在菲翔上畅享手...
ios系统打车跟安卓系统打车,... 你有没有发现,现在打车APP真是越来越方便了!不过,你知道吗?iOS系统和安卓系统在打车APP上可是...
安卓机系统更新几年,性能与体验... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你好好捋一捋,看看安卓...