面试经典问题 —— 链表之返回倒数第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）

小结

无疑，本题是很简单的。但是不要小瞧了简单题
从这道题可以学到双指针的基本解题场景
使用双指针方法的关键在于理解何时以及如何移动指针，这通常依赖于当前指针所指向元素之间的关系。