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

思路：求一个链表的后k个节点。

            可以先求链表的总长度，用总长度减去k,就可以得到从前往后顺步走的长度。

class Solution {
public:
    
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode *p=pHead;
        int n=0;//链表的大小
        while(p!=nullptr){
            n++;
            p=p->next;
        }
        if(n<k)//如果链表小于k,则返回空
            return nullptr;
        n-=k;//总数-倒数的数=顺步走的次数
        
        p=pHead;
        while(n--){//遍历
            p=p->next;
        }
        return p;
    }
};

时间复杂度：

空间复杂度：

思路：
            p指针和q指针都指向头结点，再让q指针移动k步，这样就能让p指针和q指针的间隔是k。
            而后p指针和q指针一起移动，直到q指针到达边界（即null）,则输出p指针。

class Solution {
public:
    
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode *p=pHead,*q=pHead;//初始化
        
        while(k&&q!=nullptr){//先让q指针移动k步，这样就能让p指针和q指针的间隔是k
            k--;
            q=q->next;
        }
        if(k==0){
            while(q!=nullptr){//p指针和q指针一起移动，直到q==null
                p=p->next;
                q=q->next;
            }
            return p;//返回p
        }else{//如果链表小于k,则返回空
            return nullptr;
        }
        
    }
};

时间复杂度：

空间复杂度：