面试经典问题 —— 链表之返回倒数第k个节点（经典的双指针问题）
目录
- 原题
- 思路
- 代码实现
- 小结
原题
leetcode链接 ：
https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
思路
这题就是典型的双指针母题
第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。
代码实现
first指针是快指针（fast），second指针是慢指针（slow）
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode *fast= head, *slow = head;
for (int i = 0; i < k; i++)
fast = fast->next;
while (cur != nullptr) {
fast = fast->next;
slow = slow->next;
}
//此时slow指针就停在了目标节点的前一个节点
return slow->val;
}
};
复杂度分析：
显然，时间复杂度为O（N）空间复杂度为O（1）
小结
无疑，本题是很简单的。但是不要小瞧了简单题
从这道题可以学到双指针的基本解题场景
使用双指针方法的关键在于理解何时以及如何移动指针，这通常依赖于当前指针所指向元素之间的关系。