算法打卡Day14_剑指offer22 链表中倒数第k个节点

简介: 算法打卡Day14_剑指offer22 链表中倒数第k个节点

剑指offer 原题

热度 【美团】

输入一个链表,输出该链表中倒数第k个节点,为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第一个节点,

例如,一个链表有6个节点,从头节点开始,他们的值依次是1、2、3、4、5、6.这 个链表的倒数第3个节点的值是值为4的节点。

思路

方法一 hash表获取

我们将遍历链表以后将数值存入hash表。《位置,节点》、然后计数出倒数的是第几个节点,如n是链表的长度,要求取到倒数第k个数,那么倒过来计算正数的值就是

n-k+1。 直接去hash.get(n-k+1).得到节点值。

时间复杂度为O【n】.

空间复杂度为O【n】

方法二 快慢指针

如果要求时间复杂度是O(n),空间复杂度是o(1) 。那么hash就 不符合要求了。这时就得另辟蹊径。


这个时候我们,想到了使用快慢指针的方式。快慢指针首先都同时指向链表头head。若我们要取倒数第2个节点的值。,设k=2 .那么快指针先走k-1步。即快指针先移动(2-1)=1步。

20200401134307494.png

然后此时慢指针始终笔快指针慢1步。快慢指针同时移动,直到快指针到达链表尾部时。慢指针恰好指向链表后的倒数第2个节点。我们刚好能取到倒数第2个节点的值

20200401134307494.png

这方法还真是巧妙至极,简直是妙蛙种子走进了家了,妙妙妙啊 ~

有兴趣的老爷,还可以关注我的公众号【一起收破烂】,回复【006】获取 最新java面试资料以及简历模型120套哦~

相关文章
|
9天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
2天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
9 2
|
2天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
7 0
|
2天前
|
算法
二叉树删除节点算法---递归
二叉树删除节点算法---递归
|
5天前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
6天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
8天前
|
存储
删除链表的节点
删除链表的节点
5 0
|
10天前
|
存储 SQL 算法
|
10天前
|
SQL 算法 数据挖掘
力扣题目 19:删除链表的倒数第N个节点 【python】
力扣题目 19:删除链表的倒数第N个节点 【python】
|
5天前
|
算法 JavaScript 决策智能
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。