003

/**
 *实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
 *
 * 示例输入： 1->2->3->4->5 和 k = 2
 * 输出： 4
 * 说明：给定的 k 保证是有效的。
 */
 
/** 解法一：快慢指针，不改变head */
class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode slow=head , fast=head;
        while(k!= 0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
}

/**  解法2：快慢指针，改变head，虽然占用内存较少，但不推荐 */
class Solution {
    public int kthToLast(ListNode head, int k) {
         ListNode fast=head;
        while(k>0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            fast=fast.next;
           head=head.next;
        }
        return head.val;
    }
}