快慢指针法

快指针比慢指针快k步，当快指针为空时，慢指针刚好指向倒数第k个

• 快慢指针的思路来源于相对距离，倒数第k个->两个指针相差k步保持不变

判断长度是否符合要求，应该用k是否等于0而不是快指针为空，当第一个就是倒数第k个，快指针为空符合要求。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode* fast=pHead;
        ListNode* slow=pHead;
        while(fast&&k)
        {
            k--;
            fast=fast->next;
        }
        if(k)
        {
            //k不为0
            return nullptr;
        }
        while(fast&&slow)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

递归法

递归满足倒序遍历，倒序数到第k个。

• 递归终止条件空指针。
• 保证值在递归函数传递或者不受影响，有三种方式全局变量，返回值，引用。
• 这里k和k_node都不能受影响，一个作为返回值，一个作为全局变量。
• 返回result-1不受if影响，保证result改变，如果不变，则k_node会被每层函数的pHead赋值。
• k_node初始值为空，使得不符合条件时直接返回空。

class Solution {
public:
    ListNode* k_node=nullptr;
    int recrusion(ListNode* pHead,int k)
    {
        if(!pHead)
        {
            return k-1;
        }
        int result=recrusion(pHead->next, k);
        if(result==0)
        {
            k_node=pHead;
        }
        return result-1;
    }
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        int result=recrusion(pHead,  k);
        return k_node;
    }
};

遍历法

遍历出长度，进行判断k是否合法，再求解出倒数第k个