解法一：非递归

1、思路

• 一个快指针先走k步，再两指针齐步走直到快指针走到链表尾；

• 此时慢指针指向的就是倒数第k个节点。

2、代码

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        auto fast = head, slow = head;
        while (k -- )
        {
            fast = fast->next;  //快指针先走k步
        }

        while (fast)
        {
            fast = fast->next;  //快慢指针齐步走
            slow = slow->next;
        }

        return slow->val;
    }
};

解法二：递归

1、思路

• 按引用传递一个参数i，表示当前递归到倒数第i个节点；

• 递归到最后一层，也就是空节点时，返回0，这时开始递归返回；

• 此时分三种情况：
  1、还没有到达倒数第k个节点，直接返回0；
  2、刚好到达倒数第k个节点，返回当前节点的值；
  3、已经超过了倒数第k个节点，返回之前保存的倒数第k个节点的值。

2、代码

class Solution {
public:
    int helper(ListNode* head, int k, int& i)
    {
        if (head == nullptr) return 0;

        int val = helper(head->next, k, i);
        ++ i;

        if (i < k)              //情况1、
        {
            return 0;
        }
        else if (i == k)        //情况2、
        {
            return head->val;
        }
        else                    //情况3、
        {
            return val;
        }
    }

    int kthToLast(ListNode* head, int k) {
        int i = 0;
        int res = helper(head, k, i);

        return res;
    }
};