yxc题解
算法
(链表) $O(n)$
由于单链表不能索引到前驱节点，所以只能从前往后遍历。

我们一共遍历两次：

第一次遍历得到链表总长度 n；
链表的倒数第 k 个节点，相当于正数第 n−k+1 个节点。所以第二次遍历到第 n−k+1 个节点，就是我们要找的答案。
注意当 k>n 时要返回nullptr。

时间复杂度
链表总共遍历两次，所以时间复杂度是 $O(n)$。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        int n = 0;
        auto p = pListHead;
        while (p != NULL) {
            n ++;
            p = p->next;
        }
        if (k > n) return NULL;
        for (int i = 1; i <= n - k; i ++) pListHead = pListHead->next; //往后跳n-k步
        return pListHead;
    }
};

yxc代码

class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;
        if (n < k) return nullptr;
        auto p = head;
        for (int i = 0; i < n - k; i ++ ) p = p->next;
        return p;
    }
};