题解 | #链表中倒数最后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) {
        // write code here
        //双指针法
        ListNode* p1=pHead,* p2=p1;
        while(k!=0&&p2!=nullptr)
        {
            --k;
            p2=p2->next;
        }
        if(k==0)//移动到了指定位置
        {
            while(p2!=nullptr)//将前面的指针移动到最后
            {
                p2=p2->next;
                p1=p1->next;
            }
            return p1;
        }
        else//不能移动到返回空
        {
            return nullptr;
        }
    }
};

牛客官方题解

我们无法逆序遍历链表，就很难得到链表的倒数第k个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第k的位置上，即距离链表尾的距离是k，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是k。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施。

具体做法：

• step 1：准备一个快指针，从链表头开始，在链表上先走�k步。
• step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是�k。
• step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数�k个元素的位置。