剑指offer-JZ14

题目描述
输入一个链表，输出该链表中倒数第k个结点。
如果该链表长度小于k，请返回空。

C++
两种思路：暴力法+双指针。
需要注意一些边界条件：

1. 链表为空，暴力可以用，但是双指针需要处理
2. 
3. 输出的是链表，需要保函后面的信息。

方法一：
我们先用暴力思路来看，如果给出的是正数第K个，则只需要一个遍历+边界判断即可。

现在是倒数第K个，那么就是正数 个，这里 是链表长度。
因此，现得到n,然后按照之前的套路输出即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        // bundary condiation
        if(nullptr == pHead || k<=0){
            return nullptr;
        } 
        // grady
        int num=0;
        ListNode* current = pHead;
        while(current != nullptr){
            num=num+1;
            current=current->next;
        }

        if(k>num){
            return nullptr;
        }
        current = pHead;
        for(int i=0; i<num-k;i++){
            current=current->next;
        }
        return current;
    }
};

计算一下，这个暴力时间复杂度是
空间复杂度

方法二：双指针
如果构建2个指针，距离为K，即指针p的后K个指针q，当q指向末尾的时候，p就是倒数第k个。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        // bundary condiation
        if(pHead == nullptr || k<0) return nullptr;
        // create two pointer
        ListNode* first = pHead;
        ListNode* second = pHead;
        // setting k steps
        for(int i=0; i<k; i++){
            if(first == nullptr) return nullptr; 
            first = first->next;
        }
        // go to end
        while(first!=nullptr){
            first =first->next;
            second = second->next;
        }
        return second;
    }
};