题目
输入一个链表，输出该链表中倒数第k个结点。
分析一
我最开始的想法就是使用栈，先把全部的节点压入栈内，那么最后一个节点一定在栈顶，那么我弹出K个就好，最后一个就是结果。
这个方法是可以通过牛客网的测试的，但是感觉利用了额外的空间，不一定是最好的。
代码一
// 方法一
public ListNode FindKthToTail1(ListNode head,int k) {
if ((head == null)) {
return null;
}
// 记录一共有多少个节点
int count = 0;
Stack<ListNode> stack = new Stack<>();
while (head != null) {
stack.push(head);
count ++;
head = head.next;
}
// 如果要输出的节点的个数大于了链表节点的个数，直接返回
// k为0 也不行
if (k > count || k <= 0) {
return null;
}
int i =0;
ListNode result = null;
while ( i < k) {
i++;
result = stack.pop();
}
return result;
}
分析二
链表采用非连续地址存储，所以节点中都会存储下一个节点的信息，有的链表还会同时存储上一个节点和下一个节点的信息。因此链表相比于数组来说，输出指定位置的 元素并不那么容易。需要进行遍历操作，这是无法逃脱的。
这个题，我们首先要考虑：
（1）链表为空时，直接返回null； （2）k的值<1的时候，也不正确； （3）k的值超过链表长度也不正确。
这时候，很简单的一种思路就是，设置一个count，然后遍历链表，得到链表的长度，用count记录，倒数第k个值就是第count - k + 1个节点，再次遍历链表， 输出这个节点。;
第二种思考，也是我的解法是，用一个标尺去量，标尺的长度就是k,我将标尺从，链表的开头移动到链表的结尾，标尺的结尾对着链表的结果，标尺的长度是k， 那么标尺的开始就是我们要找的第k个节点。这只是我的比喻，这样去理解。 具体的操作是定义两个指针，一个first和second,同时指向链表开头：
first先开始从链表的开头移动到k-1，second指针指向链表的开始： 假如k=3,也就是返回倒数第3个元素。
这个时候相当于“尺子”长度已经确定，只需要将“尺子”移动到链表的最后面：
代码二
// 方法二
public ListNode FindKthToTail2(ListNode head,int k) {
if (head == null || k <= 0) {
return null;
}
ListNode pFirst = head;
ListNode pSecond = head;
for(int i = 0; i < k ;i++){
if (pSecond == null) {
return null;
}
pSecond = pSecond.next;
}
while (pSecond != null) {
pSecond = pSecond.next;
pFirst = pFirst.next;
}
return pFirst;
}
