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

第6题 快慢指针 先走k个

还有一种没写，就是直接遍历并且保存下来，到时候 直接找最后第k个

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        if (pHead==NULL)
            return pHead;
        // write code here
        // 还有一种就是一边走 一边存到数组，存下来以后，最后返回指定要的那个
        
        // 快慢指针 先走k个
        // 再一起走，先走的到终点了，就说明一起走的另一个 后面还剩k个
        ListNode *p = pHead;
        ListNode *q=pHead;
        // 先走k个
        // 要注意 k的长度可能会超过 链表本身的长度的！！
        while(k!=0)
        {
            k--;
            // 如果说 长度正好是k个，拿倒数第k个正好是自己
            // 如果说 长度超过了，则返回空
            if(p->next==NULL){
                if(k==0)
                    return q;
                else
                    return NULL;
            }
            p=p->next;
        } 
        
        // 第二步 开始一起走，先走的一个走到结尾，另一个就是答案
        while(p!=NULL)
        {
            p=p->next;
            q=q->next;
        }
        return q;
    }
};