剑指offer-- 链表中倒数第K个结点

解法1

用一个p指针指向 head 然后 一直遍历到末尾，得到链表长度len 计算出你自己需要遍历的长度 len-k ；然后在遍历len-k个结点 就得到了倒数第k个结点

/*
 运行时间：14ms 占用内存：9720KB
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p = head;
        int len = 0;
        while(p!=null){
            p = p.next;
            len++;
        }
        if(len<k){
            return null;
        }else{
            int num = len - k;
            while(num>0){
                head = head.next;
                num --;
            }
            return head;
        }
    }
}

解法2

用两个指针记住头结点 ，一个指针先走k步 ，第二个指针在和第一个指针一起走，直到第一个指针走到了null，那么第二个指针就是倒数第K个结点

/*
运行时间：13ms 占用内存：9620KB
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p = head;
        ListNode q = head;
        while(k>0){
            if(p != null)
                p = p.next;
            else{
                return null;   
            }
            k--;
        }
        while(p != null){
            p = p.next;
            q = q.next;
        }
        return q;
    }
}