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

以下方法还是自己在纸上画一画，while 、 for出来的指针的位置。

方法一：这其实是一个数学题，返回倒数k个节点。那么总长度为n，个人感觉最直观的方法就是指针p先走n-k步，这个时候p指针指向的就是倒数第k个节点。然后直接返回p即可。

public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        int n = 0;
        //输入k不合法，直接返回
        if(k <= 0) return nullptr;
        ListNode* p = pHead;
        while(p){
            p = p->next;
            n++;
        }
        //长度小于k。返回
        if(n < k) return nullptr;
        p = pHead;
        for(int i = 0; i < n - k; i++){
            p = p->next;
        }
        return p;
    }
};

方法二：双指针，先让指针p_fisrt从phead开始走k步，然后让指针p_second从pHead开始走。最后当p_first遍历完整个链表，那么p_second就是指向倒数第k个节点

public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        int n = 0;
        ListNode* p_first = pHead;
        ListNode* p_second = pHead;
        //这里先用p_first计算一下长度
        while(p_first){
            p_first = p_first->next;
            n++;
        }
        if(n < k) return nullptr;
        if(k <= 0) return nullptr;
        p_first = pHead;
        //先让p_first走k步
        for(int i = 0; i < k; i++){
            p_first = p_first->next;
        }
        while(p_first){
            p_first = p_first->next;
            p_second = p_second->next;
        }
        return p_second;
    }
};

方法三：可以用栈的思想。先将整个链表入栈，然后再出栈k个节点，对出栈的每个节点链接到它的上一个节点，。

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        int n = 0;
        stack<ListNode*> s;
        ListNode* p = pHead;
        while(p){
            s.push(p);
            p = p->next;
            n++;
        }
        
        if(n < k) return nullptr;
        if(k <= 0) return nullptr;
        
        ListNode* pre = nullptr;
        for(int i = 0; i < k; i++){
            ListNode* cur = s.top();
            s.pop();
            cur->next = pre;
            pre = cur;
        }
        return pre;
    }
};