链表中倒数最后k个结点【Java版】

1）标准的 双指针法

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode pre = pHead;//head是第一个节点
        ListNode res = pHead;
        while(--k >= 0){
            if(pre== null)return null;//倒数第k的k值大于链表总长度
            pre=pre.next;
        }
        while(pre!=null){
            pre=pre.next;
            res=res.next;
        }
        return res;
    }
}
//时间 O(N)
//空间 O(1)

2）朴素方法（可读性好，且性能相当）

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int len =0;
        ListNode p = pHead;
        while(p != null){
            p = p.next;
            ++len;
        }
        if(len<k)return null;
        p = pHead;
        for(int i=1; i<=len-k; ++i){
            p=p.next;
        }
        return p;
    }
}
//【个人认为】前后指针的方法，其实和朴素的方法没有实质的性能差别。==>感觉只能炫技而已，华而不实
//时间上：两种方法的遍历都是 一个指针完整遍历N跳，另一个/另一次遍历N-k跳；
//空间上：朴素方法只要一个节点指针，前后节点法占用两个节点指针；
//总的来说，就是【一个指针遍历两次，和两个指针遍历一次】这样子，性能上，并没有两倍的时间差别