题解 | #链表中倒数最后k个结点#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //方法一：遍历链表，时间大概需要：260ms
        //特殊值处理，空链表
//        if(pHead == null){
//            return null;
//        }
//        int size = 0;  //计数器，统计链表的节点个数
//        ListNode head0 = pHead;
//        while (head0 != null){//统计链表的节点个数
//            size++;
//            head0 = head0.next;
//        }
//        head0 = pHead;
//        //特殊值处理，当链表长度小于k时，返回一个长度为 0 的链表
//        if(k > size){
//            return null;
//        }
//        //遍历链表，查找倒数第k个节点
//        while (size > k){
//            head0 = head0.next;  //节点移动
//            size--;
//        }
//        return head0;  //返回倒数第k个节点

        //方法二：利用快慢指针，时间大概需要：250ms
        ListNode fast = pHead;  //创建一个快指针
        //当快指针不为空。且k>0时，快指针移动
        while (fast != null && k > 0){
            fast = fast.next;
            k--;
        }
        //当快指针为空时，代表：链表长度小于k，请返回一个长度为 0 的链表
        if(fast == null && k > 0){
            return null;
        }
        ListNode flow = pHead;  //创建一个慢指针,指向链表的头节点
        //遍历链表，直到快指针指向空指针，此时慢指针指向倒数第k个节点
        while (fast != null){
            fast = fast.next;  //快指针移动
            flow = flow.next;  //慢指针移动
        }
        return flow;
    }
}