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

思路:

定义快慢指针fast和slow,第一次用fast遍历链表制造fast与slow符合题意的距离差,第二次fast和slow同时遍历链表当fast为null,此时slow即为答案. 开始要注意对链表判空,以及对k的合理性判断,k应>0且<链表的长度,而我们能在开始判断k是否大于0.第一次循环的终止条件是k==0或者fast==null,当第一次循环结束后如果k!=0,则k比链表的长度长不合理,返回null

时间复杂度

O(N)

空间复杂度

O(1)

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k<1) return null;
        ListNode slow=head; 
        ListNode fast=head;
        while(k!=0&&fast!=null){
            fast=fast.next;
            k--;
        }
        if(k!=0) return null;
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}