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

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

题目描述

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

image-20260928235341852

题意分析

在单链表中找到倒数第 k 个节点，返回它保存的值。倒数从一开始计数，倒数第一个是尾节点，倒数第链表长度个是头节点。

题目保证 k 有效，因此目标一定存在。需要区分这个接口与返回节点对象的题目：定位过程相同，但这里最终返回的是节点值。

解法：快慢指针固定间距

核心思路

[!blue]

单链表只能向后走，无法从尾部反向数节点。可以用两个指针形成固定间距，让前面的指针负责判断什么时候到达链尾，后面的指针自然停在目标位置。

两个指针先都指向头节点，让 fast 单独走恰好 k 次后继。此时从 slow 出发走 k 次就能到达 fast；之后两个指针每轮同时前进一步，这个距离始终不变。

循环以 fast 到达尾节点之后的空位置为终点。此时从 slow 到空位置恰好还需走 k 次后继，说明从 slow 开始直到尾节点共有 k 个节点，所以 slow 正是倒数第 k 个。

预走 k 步和终点选择空节点必须配套。若 k 等于链表长度，预走后 fast 已为空，slow 不再移动，正好返回头节点；若 k == 1，两个指针相差一步，快指针越过尾部时慢指针就停在尾节点。

解题步骤

  1. 令 fast、slow 都指向头节点。
  2. 将 fast 向后移动恰好 k 步，建立固定间距。
  3. 只要 fast 非空，就让两个指针各向后移动一步。
  4. 循环结束后返回 slow.val。

代码实现

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

func kthToLast(head *ListNode, k int) int {
    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.Val
}

复杂度分析

设链表长度为 $n$。

  • 时间复杂度：$O(n)$，快指针总共走到链尾后的空位置，慢指针至多移动 $n-k$ 次。
  • 空间复杂度：$O(1)$，只维护两个指针，不修改链表。

关键点总结

[!green]

  • 用固定间距把“从尾部计数”转成“前指针到终点时后指针的位置”。
  • 先走 k 步对应以空节点为终点，二者必须成套使用。
  • k 合法时目标自然存在，返回它的值即可。

易错点总结

[!yellow]

  • 先走 k - 1 步却仍等快指针到空位置，会让慢指针多走一步。
  • 先走 k 步后又在快指针到尾节点时停止，会提前结束，得到目标前一个节点。
  • 同步阶段只移动一个指针，会破坏固定间距。
  • 循环条件应先判断快指针是否为空，不能在空指针上访问后继。
  • 不要返回节点对象或头节点值，接口要求的是定位后慢指针的节点值。

相似题目

题目 难度 关联与区别
剑指 Offer 22. 链表中倒数第k个节点 简单 定位倒数第k项的方法相同，原题返回节点本身，本题返回节点值，接口不能直接混用。
19. 删除链表的倒数第 N 个结点 中等 原题还要删除倒数第n项，需定位前驱，本题只读取目标节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/70364269
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！