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

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

题目描述

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

image-20250507192744021

image-20241107205244010

题意分析

输入单链表的头节点 head 和正整数 k，要求返回倒数第 k 个节点本身。返回的是节点引用，判题会把它当作一条子链表打印出来，所以答案是「该节点及其之后的全部节点」，既不是节点值，也不需要把后面截断。

单链表的性质决定了两件事：只能从头往后单向走，不能回退；长度不能 $O(1)$ 拿到。所以「倒数第几个」这种从尾部起算的位置，必须先转换成从头部起算的位置——如果长度是 n，倒数第 k 个就是从头数第 n - k + 1 个，即下标 n - k。整道题的难点全部集中在「怎么在不知道 n 的情况下走出 n - k 步」。

题目保证 k 合法（不超过链表长度），因此代码不必为 k 过大兜底；反过来说也不能靠「k 越界就返回空」这种兜底逻辑来掩盖偏移量算错的问题。

边界情形有三类：k 恰好等于链表长度，答案就是头节点，此时先走的那个指针在同步阶段开始前已经是空；k = 1，答案是尾节点；链表只有一个节点。

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

核心思路

让 fast 先走 k 步，再让 fast 和 slow 同速前进。两者始终相距 k 个节点；当 fast 到达链表末尾后的 null 时，slow 恰好指向倒数第 k 个节点。

解题步骤

  • fast 和 slow 都从头节点出发。
  • fast 先前进 k 步，建立固定间距。
  • 当 fast != null 时，两个指针同时前进一步。
  • fast 到达 null 后返回 slow。

代码实现

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

        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

    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

复杂度分析

  • 时间复杂度：$O(n)$，fast 只遍历链表一次。
  • 空间复杂度：$O(1)$。

关键点总结

  • fast 必须先走 k 步，而不是 k - 1 步。
  • 两个指针同步移动可保持固定间距，无需提前计算链表长度。
  • 题目保证 k 合法，因此预走阶段不需要额外判空。

易错点总结

  • 预走 k - 1 步会让答案向后偏一位。
  • 同步循环写成 fast.next != null 会少移动一次，且 fast 可能已经为空。
  • 只移动 fast 而忘记移动 slow，最终会错误地返回头节点。
  • 题目要求返回节点本身，不能只返回节点值或截断后续链表。

相似题目

题目 难度 考察点
19. 删除链表的倒数第 N 个结点 中等 要删除而不是返回，指针必须停在目标的前驱，并用哑节点统一处理「删的是头节点」
141. 环形链表 简单 固定的是速度差而不是间距，靠两指针能否相遇判环，循环不再以走到 null 为唯一出口
142. 环形链表 II 中等 相遇之后还要靠一段等式推出入环点，指针关系是解方程解出来的而非人为设定
876. 链表的中间结点 简单 用速度比 1:2 代替固定间距，额外要决定偶数长度时取前一个还是后一个中点
LCR 021. 删除链表的倒数第 N 个结点 中等 与 19 题同题换皮，适合专门练哑节点加双指针的组合写法
面试题 02.02. 返回倒数第 k 个节点 简单 指针逻辑与本题完全一致，但要求返回的是节点的值而不是节点引用