小学生都能看懂的| #链表中倒数最后k个结点#

故事背景

想象你和你的朋友在一条长长的队伍中排队。你们的任务是找到队伍中从队尾数起的第 k 个人。如果队伍不够长，那么任务失败，你们要回去重新排队。

游戏规则

1. 准备两个小朋友：
1. 一个小朋友叫“先跑”，他跑得比较快。
2. 另一个小朋友试“跟跑”，他跑得比较慢。
2. 开始游戏：
1. 让“先跑”和“跟跑”都站在队伍的最前面。
3. 跑步比赛：
1. “先跑”先向前跑 k步。
2. 然后，“先跑”和“跟跑”同时开始向前走，每次走一步。
4. 找到目标人：
1. 当“先跑”走到队伍的最末端时，“跟跑”所在的位置就是从队尾数起的第 k个人。
2. 如果“先跑”走完 k 步就已经到了队伍的末尾，说明队伍太短，任务失败。

详细步骤

1. 准备两个指针：
1. 假设队伍就是我们的链表，每个排队的人就是一个节点。
2. 我们有两个指针：“先跑”和“跟跑”。
2. 先跑先走：
1. 让“先跑”先向前走 k 步。
2. 如果“先跑”走完 k 步还没有到达队伍的末尾，说明队伍足够长。
3. 同时前进：
1. 让“先跑”和“跟跑”同时向前走，每次走一步。
4. 找到目标：
1. 当“先跑”走到队伍的末尾时，“跟跑”所在的位置就是我们要找的目标节点。

代码实现

让我们来看一看用Java实现这个逻辑的代码：

public class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // Step 1: 初始化两个指针
        ListNode leader = head; // 先跑
        ListNode follower = head; // 跟跑

        // Step 2: 让leader先走k步
        for (int i = 0; i < k; i++) {
            if (leader == null) {
                return null; // 队伍太短，任务失败
            }
            leader = leader.next;
        }

        // Step 3: 同时移动两个指针
        while (leader != null) {
            leader = leader.next;
            follower = follower.next;
        }

        // Step 4: follower所在的位置就是目标节点
        return follower;
    }
}

示例解释

假设输入为 {1, 2, 3, 4, 5}, 2：

1. 初始化指针：
1. 让“先跑”先走 2 步，此时“先跑”指向节点 3，“跟跑”指向节点 1。
2. 同时移动指针：
1. 当“先跑”走到链表的末尾时，“跟跑”正好指向节点 4。

最终输出结果为 找到的节点值为：4, 接下来的节点值为：5。

如果这篇文章对你有帮助，请点个免费的赞👍。让它能帮助到更多人。