题解 | #链表中倒数最后k个结点#
链表中倒数最后k个结点
https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if (pHead == null || k <= 0) {
return null;
}
ListNode slow = pHead;
ListNode fast = pHead;
// 先让fast指针移动k步
for (int i = 0; i < k; i++) {
if (fast == null) {
return null; // 链表长度小于k，返回null
}
fast = fast.next;
}
// 然后同时移动slow和fast指针，直到fast指针到达链表末尾
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow; // 此时slow指向倒数第k个节点
}
}
这个问题的思路是使用快慢指针来实现在单链表中找到倒数第 k 个节点。具体的步骤如下：
- 创建两个指针，一个称为 slow，另一个称为 fast。初始化它们都指向链表的头节点。
- 让 fast 指针先向前移动 k 步。这样，fast 指针就领先 slow 指针 k 个节点。
- 同时移动 slow 和 fast 指针，直到 fast 指针到达链表的末尾。由于 fast 指针领先 slow 指针 k 个节点，当 fast 指针到达末尾时，slow 指针就会指向倒数第 k 个节点。
- 返回 slow 指针所指向的节点。
这种方法的关键在于初始化时先让 fast 指针领先 k 个节点，然后同步移动两个指针，使它们的距离保持为 k，这样当 fast 指针到达末尾时，slow 指针就会指向倒数第 k 个节点。
这个思路适用于空间复杂度 O(n) 和 O(1) 的两种实现方式。在空间复杂度 O(1) 的实现方式中，我们不需要使用额外的数据结构来存储节点，只需要两个指针即可。