面试题15：链表中倒数第k个结点

题目：

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计算，即链表的尾结点是倒数第k个结点。例如一个链表有6个结点，从头开始他们的值一次是1、2、3、4、5、6.这个链表的第3个结点是值为4的结点。

思路：

定义两个指针pAhead,pBehind。
1）第一个指针pAhead从链表的头部开始遍历，先走k-1步。（此时pAhead位置在链表的第k位置，头指针为第1个位置）
2）到第k步，第二个指针pBehind也开始遍历。此时两个指针的距离保持在k-1.
3）接着，两指针一起移动。当第一个pAhead到达链表的尾结点时，第二个指针pBehind刚好在链表倒数第k结点。

注：难点是搞清楚两个指针之间的位置关系，倒数第k位置，那么他们距离应相隔k-1。
同时，需考虑输入的链表为空，链表没有k个结点的特殊情况。

解答：

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        //特殊情况测试用例
        solution.FindKthToTail(null, 0);
        //普通测试用例{1,2,3,4,5}，1略
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode pAhead = head;
        ListNode pBehind = null;

        //前一个指针先走k-1步
        int times = 1;
        while (times++ < k) {
            if (pAhead.next != null) {
                pAhead = pAhead.next;
            } else {
                return null;
            }
        }

        // 第k步，第二个指针也从头开始遍历链表。两指针距离保持在k-1
        pBehind = head;
        //两个指针一起移动，当前一个指针到达尾结点，后一个指针正好在倒数第k个结点
        while (pAhead.next != null) {
            pAhead = pAhead.next;
            pBehind = pBehind.next;
        }
        return pBehind;
    }
}