LeetCode 剑指 Offer 22. 链表中倒数第k个节点

约 4 分钟
文章信息 21 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 100-200 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 阿里 微软 美团 京东 小米 百度 快手 虾皮 贝壳 度小满 猿辅导
标签
双指针 链表 快慢指针问题

题目描述

✅ 剑指 Offer 22. 链表中倒数第k个节点

image-20261001230752546

题意分析

链表从尾部向前数，尾节点是倒数第 1 个，要求返回倒数第 k 个节点本身。返回后，这个节点原有的后继关系仍然保留，不需要截断链表，也不是只返回节点值。

单链表只能沿 next 向后移动，不能从尾部直接倒着数。题目保证链表非空，且 1 <= k <= n，其中 n 是链表长度，因此目标节点一定存在。

解法：快慢指针保持 k 步间距

核心思路

[!blue]

如果知道链表长度 n，倒数第 k 个节点就是从头开始的第 n - k + 1 个节点，也就是从头节点前进 n - k 步的位置。关键是不用提前遍历一遍计算 n，仍然让一个指针恰好走这 n - k 步。

让 fast、slow 都从头节点出发，先让 fast 单独前进 k 步。此后两者每轮都前进一步，它们之间就始终保持 k 次后继跳转的距离；这里的间距按跳转次数计算，不是两指针之间夹着的节点个数。

从头节点走到尾节点后的空位置一共需要 n 步。fast 已经预先走了 k 步，剩下恰好还要走 n - k 步，所以同步阶段结束时，slow 也只前进了 n - k 步，正好停在目标节点。

这套写法让 fast 最终停在空位置，预走步数就必须是 k。当 k = n 时，预走后 fast 已经为空，slow 不再移动，直接返回头节点；当 k = 1 时，slow 会停在尾节点。

解题步骤

  1. 将 fast、slow 都初始化为头节点。
  2. 让 fast 单独前进 k 步。题目保证 k 有效，前进过程中不会提前访问空节点的后继。
  3. 只要 fast 还不为空，就让两个指针各前进一步，保持原来的间距。
  4. fast 到达空位置时停止，返回 slow 指向的节点。

代码实现

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        // 从头节点建立 k 步间距，同步走到快指针为空时慢指针即为目标。
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast, slow := head, head

    // 从头节点建立 k 步间距，同步走到快指针为空时慢指针即为目标。
    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

复杂度分析

  • 时间复杂度：$O(n)$，快指针总共前进 n 步，慢指针前进 n - k 步。
  • 空间复杂度：$O(1)$，只使用两个指针，不保存节点集合或递归栈。

关键点总结

[!green]

  • 倒数位置可以转成从头前进 n - k 步，快指针负责感知何时已经走满 n 步。
  • 预先领先 k 步，再同步移动，就让慢指针少走恰好 k 步。
  • “预走 k 步”与“快指针停在空位置”是一组对应条件，不能单独修改其中一项。

易错点总结

[!yellow]

  • 在本写法中只预走 k - 1 步，会让慢指针多走一步，答案向后偏移；若采用另一种间距定义，终止位置也必须相应改变。
  • 同步循环不能写成 fast.next != null：这会提前停在尾节点，而且 k = n 时 fast 本身已经为空。
  • 两个指针必须同步移动，只更新快指针会破坏“慢指针走 n - k 步”的推导。
  • 返回的是原链表中的节点，不能只返回它的值，也不能为了显示单个节点而断开后继。

相似题目

题目 难度 关联与区别
19. 删除链表的倒数第 N 个结点 中等 固定间隔指针可复用，原题删除节点需要前驱，本题直接返回倒数第k个节点。
面试题 02.02. 返回倒数第 k 个节点 简单 定位相同，原题只返回值，本题返回节点并保留它后面的链接。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/72487765
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！