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

这道题的思路，第一种解法，是很容易想到的方法，我第一次就像出来了，但是，后面一种解法，我也有想到快慢指针，就是不知道怎么实现，现在清楚了，就是先核心点，

1、先让快指针走k步，之后，慢指针就跟快指针，有k步的距离，

2、如果中途还没有先走完k步距离，就到头了，就返回空指针就好了，

2、之后，再快慢指针一起走，走到结尾就返回slow指针就好了

import java.util.*;

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

public class Solution {

    /** 
     * 这是第一次，我在开头用list记录位置后，做的遍历，因为使用了list所有空间是O(n)，时间O(n)
     **/
    public ListNode FindKthToTail1 (ListNode pHead, int k) {
        if(pHead == null || k==0) {
            return null;
        }
        ListNode curr = pHead;
        List<ListNode> list = new ArrayList<ListNode>();
        while(curr!=null) {
            list.add(curr);
            curr = curr.next;
        }
        if(list.size() < k) {
            return null;
        } else {
           return list.get(list.size()-k);
        }
    }

    /*
     *  这是用快慢指针做的，刚开始我也有想到，就是不知道怎么做
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        // 快指针定位到开头第k个节点，因为i=0开始，所以具体是i-1个节点
        for(int i=0; i<k; i++) {
            if(fast != null) {
                fast = fast.next;
            } else {
                return slow = null;
            }
        }

        while(fast!=null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}