快慢指针做法

 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* p, int k) {
        auto *n = p;
        while (n && k) n = n -> next, -- k;
        if (k) return nullptr;
        while (n) p = p -> next, n = n -> next;
        return p;
    }
};

牛蛙，大佬。
对了，请问下

auto *n = p;
// 换用 auto n=p;

有什么不同吗

试了一下没区别，我习惯了c的语法，所以变量还是写了指针符号

6哦！

使用递归实现

class Solution {
public:
ListNode ans;
int find(ListNode p, int k) {
if(p==NULL) return 0;
int K=find(p->next, k)+1;
if(K==k) {
ans=p;
}
return K;
}
ListNode findKthToTail(ListNode pListHead, int k) {
ans=NULL;
find(pListHead, k);
return ans;
}
};

####按照楼上大佬Fant.J的思路写的双指针是这样的，不过复杂度和y总一样的

class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        auto p = head, q = head;
        while(k--) {
            if(p) p = p->next;
            else return NULL;
        }
        while(p) q = q->next, p = p->next;
        return q;
    }
};   

为什么 p = p->next 不能用 p->val = p->next->val ; p->next = p->next->next ; 替代 ？

超简短的递归方式

    pair<int,ListNode*> fktt(ListNode* plh,int k){
        if(plh==NULL) return (pair<int,ListNode*>){0,NULL};
        pair<int,ListNode*> r=fktt(plh->next,k);
        if(r.second!=NULL) return r;
        if(r.first+1==k) return (pair<int,ListNode*>){0,plh};
        return (pair<int,ListNode*>){r.first+1,NULL};
    }
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        return fktt(pListHead,k).second;
    }

null和nullptr有什么区别吗，nullptr是指针专用吗？

NULL是C语言的，nullptr是C++11的

我刚开始用了快慢指针，然后翻车了 哈哈哈

快慢指针要稍微绕点弯hh

那是什么呀，请教一下

有个时间 复杂度更低的解法。
先让first节点走k个长度，然后first和second同时走，当first.next==null 时，second的当前节点就是答案。

这个做法不错呀哈哈
不过first一共会走n步，second一共会走n - k + 1步，和上面的做法是一样的~

时间复杂度低了呀，是O(n),上面的做法是O(n+n-k)

时间复杂度是指计算量的量级，常数会被忽略掉，比如 $O(n)$ 和 $O(2n)$ 是一样的。这个题 $k \le n$，所以 $O(n + n - k) = O(n)$

对，时间复杂度更细一点的话是O(n)和O(2n)，如果链表非常长，k是1，这种解法就会靠近O(2n)，前后指针法依然是O(n)

两个指针同时走不能只算一个指针的计算量呀~ first一共会走n步，second一共会走n - k + 1步，一共走的次数也是 $n + n - k$，是一样的。

额额，我好像只算一个指针的了，hhh，谢谢大佬耐心指教