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

核心思想

解法1：

1. 求链表长度
2. 计算len - k = index
3. 正序遍历走到index，即输出

todo

解法2：

1. 递归到尾结点
   • 统计长度的定义和累加位置很重要，函数每次进来压栈，就累加
   • 尾结点判断条件和上述挂钩，pHead->next == NULL， 则判断的是尾结点
2. 开始累加反向计数
   • 递归反向出栈一次，则反向计数累加1
   • 第一次出栈，则返回的是尾结点，当前栈的pHead即倒数第二个结点
   • 判断i == k,标记返回值位置

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    // write code here    
    // 因为是递归，且判断的尾结点条件为next，所以计算长度的len放到最开始，即每进来一次，则长度累加
    // 必须是static类型
    static int len = 0;
    len ++;
    // case1: 空链表
    if(pHead == NULL)
    {
        return pHead;
    }
    
    // 递归结尾条件，即找到尾结点返回
    if(pHead->next == NULL)
    {
        return pHead;
    }

    // 倒数第K个结点的指针pointer
    static struct ListNode * pK = NULL;
    // 递归反方向回的时候，返回指针。
    struct ListNode * tail = NULL;
    // 递归逆向往回走的计数器
    static int i = 0;

    // 找到尾结点，递归函数f(pHead->next)
    tail = FindKthToTail(pHead->next, k);
    ++i;
    // .
    if(i == k)
    {
        pK = tail;
    }
 
    // k == len, then return phead;
    if(i == len -1 && k != len)
    {
        // return pK;
        pHead = pK;
    }
    
    return pHead;
}