题解 | #链表中倒数最后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 *m=pHead;
        ListNode *n=pHead;

        while(k--){
            if(m==nullptr) return nullptr;
            m=m->next;
        }
        while(m!=nullptr){
            m=m->next;
            n=n->next;
         
        }
        return n;
    }
};

如何做，我们可以先统计长度，计算出倒数第k个长度，然后遍历到指定长度对应的位置。或者我们只需要一次遍历。不需要提取统计链表长度。我们需要维持目标节点到链表尾是倒数第k个，到最后一个节点是k-1个距离。我们是否可以使用两个指针，一个先遍历k-1次，然后两个指针再同时往后遍历，这样保持一个k-1距离，这样，先移动的到链表尾得到时候，另外一个就是刚好在倒数第k个位置。当时这里面存在问题需要处理。首先，就是如果两个指针指向头节点，其中一个指针先开始遍历，遍历多少次使得这个差正好等于，倒数第k个与尾节点的差。k-1次。或者当我们的先移动的指针指向nullptr时，说明链表结束,此时就是保持k的差距就可以。

    while(k--){
        if(m==nullptr) return nullptr;
        m=m->next;
    }

这边就是先移动m，移动k次。此时，不得不考虑另外一个问题。链表长度是否够k。如果在没有移动k次前，m=nullptr，需要加一个判断。那么这时就不存在倒数第k个。理想状态下，能找到倒数第k个。

    while(m!=nullptr){
        m=m->next;
        n=n->next;
    }

此时，nm维持这样的差。然后一起向后遍历，等到m到nullptr，n就是倒数第k个，返回n;