面试题22. 链表中倒数第k个节点

题目描述：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

思路：

1、这道题首先能够想到的就是，先从头走到链表的尾部，再回溯k步，但是本题的链表是单向链表，单向链表只有从头向后的指针，没有从后往前的指针，因此我们并没有办法回溯。
2、既然不能从后往前回溯，那么我们还是考虑从头往后遍历。如果链表有n个节点，那么倒数第k个节点，就是从头往后数第n-k+1个节点。如果我们能得到链表的长度，那么我们就需要从头向后走n-k+1步即可。如何获取链表的长度n呢？就需要我们从头向后遍历，并累计结点的个数。然后再从头向后走n-k+1。可以看出我们需要遍历2次链表。第一次计算链表的长度。第二次为了找到倒数第k个节点；
3、如何能够只遍历一次就能找到倒数第k个节点呢? 我们定义2个指针，都指向头结点。第一个指针从头结点先遍历向后走k-1，第二个指针保持不动。从第k步开始，p1走，p2也跟着走。两个指针始终保持k-1的距离，直到p1走到链表的尾节点时，p2刚好走到倒数第k个节点。

Java解法（双指针）：

class Solution {
    public int[] printNumbers(int n) {
        int maxNum = (int)Math.pow(10, n) - 1;
        int[] ans = new int[maxNum];
        for(int i = 1; i <= maxNum; i++)
        {
            ans[i-1] = i;
        }
        return ans;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof