LeetCode 面试题 02.02. 返回倒数第 k 个节点

约 4 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 字节跳动 美团 快手 滴滴 程序员面试金典（第 6 版）
标签
双指针 链表
目录

题目描述

✅ 面试题 02.02. 返回倒数第 k 个节点

image-20230305202913593

题意分析

给一条单向链表的头节点和一个正整数 k，要返回从末尾数起第 k 个节点所存的值。倒数第 1 个指的是最后一个节点，倒数第 k 个后面还跟着 k - 1 个节点。

麻烦之处在于链表是单向的：只有 next 指针，没有 prev，也没有随机访问和长度字段。想知道「离末尾多远」，就必须先以某种方式感知到末尾在哪，而末尾只能靠向前走到空指针才能发现。

题目明确保证 k 是有效的，也就是链表长度至少为 k，所以主逻辑不必为越界兜底；但如果面试官临时追加「k 可能非法」的条件，就得补上提前判空的分支。另外注意返回类型是节点的值而不是节点本身，写成返回节点会直接编译不过。边界情形包括 k 恰好等于链表长度（答案就是头节点）和 k 等于 1（答案是尾节点）。

解法：快慢指针固定间距

核心思路

问题关键： 单链表不能从尾部向前数。两趟法先求长度再定位虽然正确，但“倒数第 k 个”只需要相对距离，不需要知道总长度。

为什么用快慢指针： 让 fast 先走 k 步，再让 fast、slow 同步前进。同步阶段始终有：从 slow 出发走 k 次 next 正好到 fast。

正确性： 两个指针每轮各走一步，固定间距保持不变。当 fast 到达空指针时，从 slow 到空指针恰好还有 k 步，所以 slow 后面有 k - 1 个节点，它正是倒数第 k 个节点。

题目保证 k 合法，因此主代码不增加越界分支；若面试官取消该保证，应在预走阶段检查 fast == null，并同时约定空链表、k <= 0 的返回方式。

解题步骤

  1. fast、slow 都从头节点出发。
  2. 让 fast 先走恰好 k 步，建立固定间距。
  3. 当 fast 非空时，两指针同步前进一步。
  4. fast 为空时返回 slow.val。

口述示例： 1 -> 2 -> 3 -> 4 -> 5、k = 2。fast 先到节点 3，随后两指针同步走；fast 越过节点 5 时，slow 停在节点 4。

边界： k = 1 时 slow 最终停在尾节点；k 等于链表长度时，fast 预走后已经为空，slow 保持在头节点。

代码实现

class Solution {
    public int kthToLast(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.val;
    }
}

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

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

复杂度分析

  • 时间复杂度：$O(n)$；fast 总共走 n 步，每个节点至多访问常数次。
  • 空间复杂度：$O(1)$，只使用两个指针。

关键点总结

  • 将“距末尾的位置”转化为两个指针的固定间距。
  • 预走 k 步、循环判断 fast != null、最终返回 slow 必须配套。
  • 用空指针作为终点，可自然覆盖 k = 1 和 k = n。
  • 是否校验非法 k 取决于题目契约，不要默默假设或随意返回魔法值。

易错点总结

  • fast 只先走 k - 1 步：答案会向后偏一位。
  • 同步条件写成 fast.next != null：循环少走一步，答案向前偏一位。
  • 预走后只移动 fast：slow 会一直停在头节点。
  • 在没有“k 合法”保证时直接访问 fast.next：k 大于链表长度会触发空指针异常。

相似题目

题目 难度 考察点
19. 删除链表的倒数第 N 个结点 中等 要删除而非读取，slow 必须停在前驱，需配合哑节点
876. 链表的中间结点 简单 间距不固定，改用一步与两步的速度差来定位中点
141. 环形链表 简单 快慢指针用于判断相遇而非定位，终止条件从判空变成判相等
61. 旋转链表 中等 同样按倒数位置切断，但要先对 k 取模再重新接环
LCR 021. 删除链表的倒数第 N 个结点 中等 与 19 同源，适合对照一趟双指针与两趟计数两种写法
剑指 Offer 22. 链表中倒数第k个节点 简单 返回的是节点而非节点值，注意函数签名差异