题目描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。
最普遍的方法是，先统计单链表中结点的个数，然后再找到第（n-k）个结点。注意链表为空，k为0，k为1，k大于链表中节点个数时的情况 。时间复杂度为O（n）。代码略。 这里主要讲一下另一个思路，这种思路在其他题目中也会有应用。主要思路就是使用两个指针，先让前面的指针走到正向第k个结点 ，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点
/**
分析：设置两个指针p1、p2首先p1和p2都指向head，
然后p2向前走k步，这样p1和p2之间就间隔k个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。
*/
public static Node reGetKthNode(Node head, int k) {
// 这里k的计数是从1开始，若k为0或链表为空返回null
if (null == head)
return null;
if (k <= 0)
return null;
Node slow = head;
Node fast = head;
//移动k-1个位置
while (k > 1 && fast != null) {
fast = fast.next;
k--;
}
// 当节点数小于k(while循环结束k还是大于1)，返回null
if (k > 1 || fast == null) {
return null;
}
// 前后两个指针一起走，直到前面的指针指向最后一个节点
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// 当前面的指针指向最后一个节点时，后面的指针指向倒数k个节点
return slow;
}
递归打印出倒数第k位的值：
static int level = 0;
public static void reGetKthNodeRec(Node head, int k) {
if (head == null) {
return;
}
if (k == 1) {
return;
}
reGetKthNodeRec(head.next, k);
level++;
if (level == k) {
System.out.println(head.val);
}
}