面试题 02.02. Kth Node From End of List LCCI

Implement an algorithm to find the kth to last element of a singly linked list. Return the value of the element.

Note: This problem is slightly different from the original one in the book.

Example:

Input: 1->2->3->4->5 和 k = 2
Output: 4

k is always valid.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
      //fast 快指针 slow 慢指针
        ListNode fast = head,slow = head;
      //当k>0 进行while 此时先让快指针跑起来
        while(k > 0){
          //此时快指针 > next
            fast = fast.next;
            k --;
        }
      //判断 此时快指针继续>next
        while(fast != null){
            fast = fast.next;
          //慢指针 next
            slow = slow.next;
        }
      //也就是说 快指针一轮next2次，慢指针1次
        return slow.val;
    }
}