《剑指offer第二版》面试题22：链表中倒数第k个节点（jav

题目描述

输入一个链表，输出该链表中倒数第k个节点。比如一个链表有6个节点，从头节点开始，他们的值依次是1，2，3，4，5，6。这个链表的倒数第3个节点是值为4的节点。

解题思路:

1. 定义两个指针，fast和slow都指向链表的头节点。
2. fast先走k个节点。
3. fast和slow再同时往后遍历，等fast走到结尾的时候，slow指向的就是倒数第k个节点。

代码

ListNode findKThToTail(ListNode head, int k){
    if (k <= 0 || head == null) {
        return null;
    }
    ListNode fastNode = head;
    // fastNode先走k个节点
    for (int i = 0; i < k; i++) {
        if (fastNode == null) {
            return null;
        }
        fastNode = fastNode.next;
    }
    ListNode slowNode = head;
    // 当fastNode走到结尾的时候，slowNode就是倒数第k个节点
    while (fastNode != null) {
        fastNode = fastNode.next;
        slowNode = slowNode.next;
    }
    return slowNode;
}