牛客网（java实现）
问题描述：
输入一个链表，输出该链表中倒数第k个结点。
问题分析：
方法一：先遍历链表，算出链表节点数count，第二次直接遍历到第count-k个节点。但要注意，可能链表结点数cout小于k，此时要返回NULL。这一条件要先判断。
方法二：使用两个指针pre和cur，用pre指针遍历到第k个节点的时候（若遍历到链表末尾，k大于0，则返回空），cur指针走到第一个节点，然后两个指针同时向前遍历，距离始终保持为k-1。这样当pre.next==null时，也即走到最后一个节点的时候，cur指向的节点就是倒数第k个节点。
这样的好处是能够节省一个循环，时间复杂度会相应降低。从O(2N) 到O(N)。
注意，但是需要一个小循环让第一个指针先走到第k个指针。同时也存在结点总数小于k的问题，如果循环还没有进行到k次，而第一个指针的已经是NULL，即走到头了，那么，函数返回NULL。
算法实现：
略
参考代码：
用方法二来实现
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode pre = head;
while (pre!=null && k>0)
{
pre = pre.next;
k--;
}
//判断倒数第k个点
if (k>0)
return null;
ListNode cur = head;
while (pre != null)
{
pre = pre.next;
cur = cur.next;
}
return cur;
}
}
