【剑指Offer】14、链表中倒数第k个结点
2024-09-08 05:20:44
题目描述:
输入一个链表,输出该链表中倒数第k个结点。为了符合习惯,从1开始计数,即链表的尾结点是倒数第1个节点。例如,一个链表有6个结点,从头结点开始,它们的值依次是1,2,3,4,5,6。则这个链表倒数第三个结点是值为4的结点。
解题思路:
对于单链表来说,没有从后向前的指针,因此一个直观的解法是先进行一次遍历,统计出链表中结点的个数n,第二次再进行一次遍历,找到第n-k+1个结点就是我们要找的结点,但是这需要对链表进行两次遍历。
为了实现一次遍历,我们这里采用双指针解法。我们可以定义两个指针,第一个指针从链表的头指针开始先向前走k步,第二个指针保持不动,从第k+1步开始,第二个指针也从头开始前进,两个指针都每次前进一步。这样,两个指针的距离都一直保持在k,当快指针(走在前面的)到达null时,慢指针(走在后面的)正好到达第k个结点。注意:要时刻留意空指针的判断。
举例:
![](https://img2018.cnblogs.com/blog/1608161/202002/1608161-20200207212419980-856055424.png)
编程实现(Java):
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null)
return null;
//思路:快慢指针,快指针先走k步,慢指针从头开始,都向前进,快指针到null时,前一个正好是倒数第k个
ListNode fast=head,slow=head;
for(int i=0;i<k;i++){ //快指针先走k步
if(fast!=null)
fast=fast.next;
else
return null;
}
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
最新文章
- Emgu学习手册
- mongodb嵌套查询
- Python开发之【用户登录锁定】
- C# HttpWebRequest 绝技 转至 http://www.sufeinet.com/
- 用VS2010编C#程序扫盲 2
- const char* <;----- >; string
- centos yum 安装问题
- 【CF】135 Div2 Choosing Capital for Treeland
- 高级Bash脚本编程指南(27):文本处理命令(三)
- Android编程 获取网络连接状态 及调用网络配置界面
- SQL Server 有关EXCEPT和INTERSECT使用
- 关于UI_USER_INTERFACE_IDIOM() &; UIDevice.model
- LeetCode OJ 83. Remove Duplicates from Sorted List
- java监控函数执行时间
- 弹出式菜单(下拉菜单)实现——PopupMenu
- Linux服务器的远程IP限制
- Java 获取指定日期范围内的每个月,每季度,每一年
- 【转载】常用精品API接口汇总
- Dubbo 源码分析 - SPI 机制
- day 26 网络通讯流程 初识socke
热门文章
- not in 和 <;>; 不走索引
- Ubuntu下调整时区时间
- 【翻译自mos文章】在12c数据库中,哪种audit trail 受到支持?
- HDOJ题目3440 House Man(差分约束)
- POJ 3344 &;amp; HDU 2414 Chessboard Dance(模拟)
- Android:制作Update.zip升级包 【转】
- c# 命令行下编译c#文件 // c# file类读写文件
- git强制放弃本地更改
- kafka参数在线修改
- mybatis中if标签判断字符串相等问题