剑指offer - 链表中倒数第k个结点(Java实现)

题目链接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先求出整个链表的长度，如果要求倒数第 k 个结点，就相当于求第 n - k + 1 个结点，遍历链表，如果到达 n - k + 1 个就返回结果即可。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
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 temp = head;
        int n = 0;
        while(temp != null) {
            ++ n;
            temp = temp.next;
        }
        k = n - k + 1;
        int cnt = 0;
        while(head != null) {
            ++ cnt;
            if(cnt == k) return head;
            head = head.next;
        }
        return head;
    }
}

  思路二：快慢指针，首先我们设置两个指针 l, r。刚开始让 l 指针指向链表的第一个元素，然后 r 指针指向第 k + 1 的元素，如果在这个过程中 r 指针提前到达了 null，说明 k 大于 n，此时返回 null即可，最后我们让 l 和 r 同时移动，直到 r 指针移动到最后一个 null 的位置即可，这样在 l 和 r 之间就包含了 k 个元素，l 指针指向的就是倒数第 k 个元素。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
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 l = head, r = head;
        while(k -- > 0) {
            if(r != null) r = r.next;
            else return null;
        }
        while(r != null) {
            r = r.next;
            l = l.next;
        }
        return l;
    }
}