兰州网站建站,广州网站建设网站开发,网络营销是干嘛的,简约好看的网站模板02.02、[简单] 返回倒数第 k 个节点
1、题目描述
实现一种算法#xff0c;找出单向链表中倒数第 k 个节点。返回该节点的值。
2、题解思路
本题的关键在于使用双指针法#xff0c;通过两个指针#xff08;fast 和 slow#xff09;#xff0c;让 fast 指针比 slow 指针…02.02、[简单] 返回倒数第 k 个节点
1、题目描述
实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。
2、题解思路
本题的关键在于使用双指针法通过两个指针fast 和 slow让 fast 指针比 slow 指针先走 k 步这样当 fast 到达链表末尾时slow 正好指向倒数第 k 个节点。
具体步骤如下
初始化两个指针 fast 和 slow都指向链表的头节点。让 fast 先走 k 步使得 fast 和 slow 之间的距离为 k。同时移动 fast 和 slow直到 fast 到达链表的末尾。此时slow 指针所指向的节点就是倒数第 k 个节点返回该节点的值。
3、详细代码解析
class Solution {
public:int kthToLast(ListNode* head, int k) {// 初始化两个指针分别指向链表的头节点ListNode* fast head;ListNode* slow head;// 让 fast 指针先走 k 步while (k--) {fast fast-next;}// 同时移动 fast 和 slow直到 fast 到达链表的末尾// 当 fast 到达链表末尾时slow 则正好指向倒数第 k 个节点返回该节点的值while (fast) {fast fast-next;slow slow-next;}// slow 现在指向倒数第 k 个节点返回该节点的值return slow-val;}
};4、时间复杂度与空间复杂度
时间复杂度O(n)其中 n 为链表的长度。由于我们只遍历了链表一次因此时间复杂度是线性的。空间复杂度O(1)只用了两个指针空间开销很小。
通过使用双指针技巧我们可以在一次遍历中高效地找到倒数第 k 个节点。这个解法在不需要额外空间的情况下能够很好地解决问题。
