题解 | #链表中倒数最后k个结点#

快慢指针法

移动快指针

首先将快指针fast与k一同往前移动，直到k移出链表（k==0）或者快指针移出链表（fast==nullptr） 为止

移动慢指针

1. 判断是否有k==0，即考虑 k 是否会大于链表总长度
2. 快慢指针一同往前移动，直到快指针 fast==nullptr，然后返回 slow 指针即可。

复杂度分析：

• 空间复杂度 O(1)：只使用有限个变量slow、fast
• 时间复杂度 O(n)：需要遍历一次整个链表

代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode *f = pHead, *slow = pHead;
        while (f!=nullptr && k!=0)
        {
            k--;
            f = f->next;
        }
        if(k!=0) return nullptr;  // 快指针比k先移出链表，即大于链表时
      
        while(f!=nullptr){
            f = f->next;
            slow = slow->next;
        }

        return slow;
    }
};