题目描述：

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

分析

为了实现只遍历链表一次就能找到倒数第k个结点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1。第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针正好是倒数第k个结点。

public class Solution_22 {

    public Node findKthToTail(Node head, int k) {
        if (head == null || k <= 0) return null; //注意k的边界

        Node ahead = head;
        for (int i = 1; i < k; i++) {
            if (ahead.next != null) {
                ahead = ahead.next;
            } else {
                return null;
            }
        }

        Node behind = head;
        while (ahead.next != null) {
            ahead = ahead.next;
            behind = behind.next;
        }

        return behind;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        Node first = new Node(2);
        Node second = new Node(3);
        Node third = new Node(4);
        Node fourth = new Node(5);
        Node fifth = new Node(6);

        head.next = first;
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;

        System.out.println(new Solution_22().findKthToTail(head, 1).value);
    }

}

class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
    }
}