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

双指针

快指针先走，当走到第K个结点时，慢指针开始走，遍历完后，慢指针指向的结点就是倒数第K个结点。

C++代码：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        if (!pHead) {return NULL;}
        ListNode *l = NULL, *r = pHead;
        int i = 1;
        while (r->next) {
            if (i++ == k) {l = pHead;}
            r = r->next;
            if (l) l = l->next;
        }
        if (i == k) return pHead;
        else return l;
    }
};

空间复杂度 O(1)，时间复杂度 O(n)