LeetCode - 02.02.返回倒数第 k 个节点
目录
题目
解法一
双指针算法
原理
详细过程
为什么它有效？
时间复杂度与空间复杂度
代码
解法二
递归算法
核心思想
执行流程详解
具体例子
代码
题目
面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
解法一
双指针算法
原理
- 设置距离：快慢指针之间维持k个节点的固定距离
- 同步移动：当快指针到达链表末尾时，慢指针恰好指向倒数第k个节点
详细过程
初始化：两个指针fast和slow都指向链表头节点
head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^建立间距：让fast指针先走k步，建立k个节点的距离
例如，k=2，fast先走2步head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^同步移动：然后fast和slow同时向前移动，保持k个节点的距离
第一步同时移动：head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^第二步同时移动：head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^第三步同时移动：head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^slow^找到结果：当fast指针到达NULL（链表末尾）时，slow指针恰好指向倒数第k个节点
head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULLfast^ (已经是NULL)slow^ (这就是倒数第2个节点)为什么它有效？
这个方法之所以有效，是因为：
- 如果链表长度为n，倒数第k个节点就是正数第(n-k+1)个节点
- 当fast指针先走了k步，然后两个指针一起走，直到fast到达NULL（即走了n步）
- 此时slow指针走了(n-k)步，所以它指向的是第(n-k+1)个节点，即倒数第k个节点
时间复杂度与空间复杂度
- 一次遍历：只需要遍历链表一次，时间复杂度O(n)
- 常数空间：只使用两个指针，空间复杂度O(1)
- 无需知道链表长度：不需要预先计算链表的长度
代码
class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode* fast = head;ListNode* slow = head;for(int i = 0;i < k;i++){head = head->next;fast = head;}while(fast != nullptr){fast = fast->next;slow = slow->next;}return slow->val;}
};解法二
递归算法
核心思想
这种递归方法使用"后序遍历"的思想 - 先递归到链表末尾，然后在回溯过程中进行计数，找到倒数第 k 个节点。
执行流程详解
- 递进阶段：
- 递归函数 dfs 首先检查当前节点是否为空
- 如果不为空，继续递归调用自己，传入下一个节点：dfs(head->next, k)
- 这个过程会一直进行，直到到达链表的末尾（遇到 nullptr）
- 回溯阶段：
- 当到达链表末尾时，开始回溯
- 每次回溯一层，计数器 count 加1
- 当计数器等于指定的 k 值时，当前节点就是倒数第 k 个节点
- 将这个节点的值保存到 ret 中
具体例子
假设链表为 1->2->3->4->5，k=2（寻找倒数第2个节点）：
初始调用: kthToLast(head, 2)
- 调用 dfs(head, 2)，此时 count 为 0
递归调用展开:
dfs(1) -> dfs(2) -> dfs(3) -> dfs(4) -> dfs(5) -> dfs(nullptr)回溯过程:
- dfs(nullptr) 检测到空节点，直接返回
- 回到 dfs(5)：count++ 变为 1，1≠2，继续回溯
- 回到 dfs(4)：count++ 变为 2，2=2，设置 ret = 4
- 回到 dfs(3)：count++ 变为 3，3≠2，继续回溯
- 回到 dfs(2)：count++ 变为 4，4≠2，继续回溯
- 回到 dfs(1)：count++ 变为 5，5≠2，继续回溯
- 所有递归调用结束，ret 的值为 4
返回结果: kthToLast 返回 ret 的值，即 4
代码
class Solution {int ret;int count;
public:int kthToLast(ListNode* head, int k) {dfs(head,k);return ret;}void dfs(ListNode* head, int k){if(head==nullptr){return;}dfs(head->next,k);count++;if(k == count){ret = head->val;}}
};