题目22：链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，本题从1 开始计数，即链表的尾结点是倒数第1 个结点。

举例说明

例如一个链表有6 个结点，从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点。

思路

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

代码实现

public class _22 {
    private static class ListNode {
        int value;
        ListNode next;
        
        public ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode findKthToTail(ListNode head, int k) {
        if (k < 1 || head == null) {//k=0也不可以，会导致 k-1=0xFFFFFFFF
            return null;
        }
        ListNode cur = head;
        // 倒数第k个结点与倒数第一个结点相隔k-1个位置
        // 所以，让 cur 先走k-1个位置
        for (int i = 1; i < k; i++) {
            if (cur.next != null) {
                cur = cur.next;
            }else {// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
                return null;
            }
        }
        // cur 先走了k-1步，然后 cur 和 head 一起走，
        // 当cur走到最后一个结点即，cur.next=null时，head就是倒数第k个结点
        while (cur.next != null) {
            head = head.next;
            cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) {
        // 10 -> 20 -> 30 -> 40 -> 50 -> 60
        ListNode n1 = new ListNode(10);
        ListNode n2 = new ListNode(20);
        ListNode n3 = new ListNode(30);
        ListNode n4 = new ListNode(40);
        ListNode n5 = new ListNode(50);
        ListNode n6 = new ListNode(60);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n6;
        System.out.println("倒数第1个节点的值是："+findKthToTail(n1, 1).value); 
        System.out.println("倒数第3个节点的值是："+findKthToTail(n1, 3).value);
        System.out.println("倒数第6个节点的值是："+findKthToTail(n1, 6).value);
    }
}

输出：

倒数第1个节点的值是：60
倒数第3个节点的值是：40
倒数第6个节点的值是：10