BM8. [链表中倒数最后k个结点]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM8. 链表中倒数最后k个结点
题目分析
这个题目也是一个快慢指针问题，就是先让快指针走k步，然后快指针拉着慢指针一起走，需要判断k是否会超出数组的长度。
做法分析
定义快指针fast，和慢指针slow，快指针先走K步
ListNode fast = pHead;
ListNode slow = pHead;
while(k > 0 && fast != null){
fast = fast.next;
k--;
}
额外判断一种情况，就是给出的k是大于链表长度，这样fast已经是null，但是k不为0，所以直接返回null即可
if(fast == null && k != 0)
return null;
最后快慢指针同时向后遍历，那么最后的慢指针就应该是链表中倒数第K个节点
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
完整题解
public ListNode FindKthToTail(ListNode pHead, int k) {
ListNode fast = pHead;
ListNode slow = pHead;
while (k > 0 && fast != null) {
fast = fast.next;
k--;
}
if (fast == null && k != 0)
return null;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
复杂度分析
时间复杂度：， slow指针走过的距离不会超过链表的总长度，所以时间复杂度是
空间复杂度：没有使用额外的空间
