面试题22：链表中倒数第k个节点

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

class ListNode{
    int value;
    ListNode next;
}

思路：构建两个指针P1和P2，P1指针先向前走(k-1)步，然后P2指针开始走，这样P1和P2之间就距离(k-1)。当P1到达尾部的时候，P2指向的节点就是我们要的节点。本题重点考查鲁棒性，要考虑到非法输入情况。
解决方案：

public class Question22 {
    static class ListNode{
        public ListNode(int value){
            this.value = value;
        }
        int value;
        ListNode next;
    }
    public static ListNode findKthToTail(ListNode listHead, int k){
        if (listHead == null || k == 0) return null;
        ListNode head = listHead;
        ListNode behind = null;
        for (int i=0; i<k-1; i++){
            if (head.next != null){
                head = head.next;
            }else {
                return null;
            }
        }
        behind = listHead;
        while (head.next != null){
            head = head.next;
            behind = behind.next;
        }
        return behind;
    }

    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode pAhead = new ListNode(3);
        ListNode pBhead = new ListNode(5);
        ListNode pChead = new ListNode(7);
        pHead.next = pAhead;
        pAhead.next = pBhead;
        pBhead.next = pChead;
        System.out.println(findKthToTail(pHead, 2).value);

    }
}