题目描述
输入一个链表，输出该链表中倒数第k个结点。
做这道题时，由于受之前题目的影响，下意识地想到使用栈、数组之类的来存储链表。
方法一：使用递归，实质上是使用栈
public class Solution {
int n = 0;
ListNode res;
public ListNode FindKthToTail(ListNode head, int k) {
if (head != null) {
if (head.next != null)
FindKthToTail(head.next, k);
}
n++;
if (n == k) {
res = head;
}
return res;
}
}
方法二：使用数组
public class Solution {
public static ListNode FindKthToTail(ListNode head,int k) {
ListNode[] tmp = new ListNode[1000];
int i;
for(i = 0; head != null; i++) {
tmp[i] = head;
head = head.next;
}
return (i - k) < 0 ? head:tmp[i - k];
}
}
代码都简单易懂，就不解释了。
方法三：
遍历一遍链表得到链表长度n，再遍历一遍链表，第n－k＋1个便为所求。代码略。
虽然上述代码均能完成要求，有的有较好的时间复杂度，有的有较好的空间复杂度，有的两者都有。但是总是感觉怪怪的，不是自己想要的方法。有没有方法在只遍历一次且不需要额外空间的情况下得到答案呢？
方法四：
public class Solution {
public static ListNode FindKthToTail(ListNode head,int k) {
ListNode start = head, end = head;
for(int i = 0; i < k; i++) {
if(end == null)
return null;
end = end.next;
}
while(end != null) {
start = start.next;
end = end.next;
}
return start;
}
}
设置两个指针，让end指针与start指针相距为k，这样当end指针遍历到最后时，start指针恰好指到倒数第k个。这样只需要遍历一次，并且不需要额外空间。这才是我们想要的解法！
但是。。。问题真的这么简单吗？
上面的程序看似简单地实现了巧妙的原理，但是实际上却避开了这道题目的三个大坑。
第一坑：输入的head指针为空。由于会涉及到链表head.next操作，那么head就绝对不能为空，否则会报错。
第二坑：链表节点数小于k。仍然会因为访问null.next而报空指针错误。上述程序在end后移的过程中每一步都会判断当前是否为空，是的话直接返回null。
第三坑：输入的参数k为0。若k为无符号整数，循环条件使用的是k-1的话，k-1得到的将不是-1而是4294967295，我们又没有设置每一次均检查是否为空的话，将直接爆掉最后报空指针异常。
