题目：输入一个链表，输出该链表中倒数第k个结点。
初看题目，感觉应该是从头到尾遍历链表，然后从尾回溯K步，因为是单向链表，此路不通。换条路吧。假设链表有n个结点，要找到倒数第K个结点，就是从头开始到第n-k+1个结点，但是n如何得到呢？需要从头到尾遍历，每遍历一个结点就count+1即可，这样需要遍历两次链表才能完成任务。如何才能遍历一次链表就能找到倒数第K个节点呢？
我们可以定义两个指针，第一个指针从头开始遍历到K-1个结点，第二个指针保存不动；从第K步开始，第二个指针也开始从链表头部遍历。由于两个指针的距离保持K-1不变，当第一个指针到尾部的时候，第二个指针正好到达倒数第K个结点。
代码如下：
要考虑是否是空链表，如果K==0，如果节点数小于K的三种情况。
}*/ import java.util.*; public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(head==null||k==0){ //空指针或者k==0的时候返回null return null; } ListNode p1=head; ListNode p2=null; for(int i=0;i<k-1;i++){ if(p1.next!=null){ p1=p1.next; }else{ return null; //如果节点数小于K，返回null; } } p2=head; while(p1.next!=null){ p1=p1.next; p2=p2.next; } return p2; } }
