题目描述：输入一个链表，输出该单链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的结尾点事倒数第1个节点。例如，一个链表有6个节点，从头节点开始，他们的值依次是1,2,3,4，5,6.这个链表的导数第3个节点是值为4的节点。
问题分析：
最自然的想法：从头节点遍历到尾节点，在从尾节点回溯k步。但是由于是单链表，没有从后往前的指针，无法回溯。
新的思路：假设链表有n个节点，则倒数第k个节点是从头结点开始的第n-k+1个节点。因此只需求出n，再从头结点向后遍历至第n-k+1个节点即可。则需要2次遍历链表：第1次遍历整个链表，求出n，第二次求倒数第n个节点。每次遍历的时间复杂度为 O(n) ，总的时间复杂度为 O(n)
推荐解法：只进行1次遍历的实现。使用2个指针，第1个指针pAhead和第二个指针pBehind初始均指向头结点。pAhead先移动k-1步，pBehind保持不动。则从第k步开始，2个指针同时移动，二者始终保持k-1的距离。当pAhead移动到尾节点时，pBehind刚好移动到倒数第k个节点，返回pBehind即可。
代码如下 /** * 输入一个链表，输出该链表中倒数第k个结点。 * * key：利用两个指针，一次扫描实现； * * 思路： * p1指向头结点，先移动k-1个，此时p2指向头结点，此后两个指针同时移动； * 由于p1 p2之间始终相差k-1，则当p1指向尾节点时，p2刚好指向倒数k-1个节点，返回p2节点即可 * * 问题处理： * 1、输入空指针 * 2、k <= 0 * 3、k大于节点数目 * * @param head * @param k * @return */ public ListNode FindKthToTail(ListNode head,int k) { if(head == null) // 输入空指针 return null; if(k <= 0) // 输入负数 return null; ListNode pAhead = head; // p1先移动 k-1 for(int i = 0; i < k - 1; i++) { if(pAhead.next == null) // k大于节点数目，返回空 return null; else pAhead = pAhead.next; } ListNode pBehind = head; while(pAhead.next != null) { pAhead = pAhead.next; pBehind = pBehind.next; } return pBehind; }参考资料 剑指offer 何海涛 电子工业出版社