Java代码的两种思路(JZ14-链表中倒数第k个结点)

Java代码的两种思路
思路1：先遍历链表，看看链表的长度length是多，如果长度小于k，则直接返回null，如果等于k，直接返回pHead，如果大于k，则移动length-k步即可。

public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //思路1：可以先遍历一遍链表看看链表的长度length，然后在遍历一下，返回倒数length-k个元素
        if(pHead == null) return null;
        ListNode p = pHead;
        int length = 0;//记录链表的长度
        while(p!=null){
            length++;
            p = p.next;
        }
        if(length<k) return null;//不存在倒数第k个结点
        if(length == k) return pHead;
        if(length>k){
            int count = length - k;
            ListNode np = pHead;
            while(count>0){
                np = np.next;
                count--;
            }
            return np;
        }
        return null;
    }

思路2：直接使用两个指针，第一个指针先走k步，如果没有结束，则第二个指针和第一个指针同时移动，当第一个指针移动到链表结尾时，此时的第二个指针就是倒数第k个元素，因为第一个指针比第二个指针多走了k步，而此时第一个指针在末尾，自然第二个指针所指的就是倒数第k个！

public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode first = pHead;
        for(int  i= 0;i<k;i++){
             //如果提前结束，说明链表的长度小于k
            if(first == null) return first;
            first = first.next;
        }
        ListNode second = pHead;//第二个指针
        while(first!=null){
            first = first.next;
            second = second.next;
        }
        return second;
    }
}