BM8　链表中倒数最后k个结点¶

简单通过率 31.84%python3核心代码模式样例通过牛客 AC链表

讲解章节：链表

一句话

先量出长度再走 n-k 步，k 超过长度就交空表。

解题思路¶

这题考什么¶

「倒数第 k 个」在单链表上没法直接定位，必须先把它换算成「正数第 n-k+1 个」。换算需要长度，量长度就是一趟遍历。

这题真正的考点藏在数据范围里：k 最大到 1e9，而链表最长只有 1e5。教科书写法「快指针先走 k 步，再两指针同步走」在这里是个陷阱： k = 1e9 时那个 for 循环本身就要转十亿次。它中途会撞上 None，但只有在循环体内立刻判空并返回才停得下来，写成「走完 k 步再判断」就废了。

两趟扫描的写法完全绕开这件事：

数出链表长度 n；
k > n（含链表为空而 k > 0）时按题意返回空链表 None；否则从表头走 n - k 步，停下的节点就是倒数第 k 个。

循环次数只跟链表长度有关，与 k 的大小彻底脱钩。

数据规模与复杂度¶

n <= 1e5，节点值 0 <= a_i <= 1e9，0 <= k <= 1e9，其他语言时限 2 秒。两趟各 O(n)，合计不超过 2e5 次指针跳转，额外空间 O(1)，达到题面进阶要求。按 k 循环的写法在最坏情况下要转 1e9 次，纯 Python 的空循环大约每秒千万次，折合上百秒，2 秒时限稳超。

坑在哪¶

k 与链表长度不同量级，一切「按 k 计数」的循环都要先确认能被链尾截断。两趟扫描连这个判断都不需要，是最省心的写法；
k > n 时题面要求返回「长度为 0 的链表」，也就是 None，不是抛异常、更不是退而返回表头；
k == 0 时 n - k = n，指针正好走到链表末尾的 None，返回空表—— 「倒数第 0 个」本来就不存在，这个出口是算出来的，不是特判出来的；
返回的是节点本身，后台会把它往后的所有节点一并打印来比对，所以不能只返回节点值，也不必把后面的链截断。

样例复核¶

{1,2,3,4,5}，k = 2。第一趟数出 n = 5；k <= n，第二趟走 5 - 2 = 3 步： 1->2->3->4，停在值为 4 的节点。后台从它开始打印，得到 {4,5}，与样例一致。

参考实现¶

solutions/nowcoder/BM8/sol.py
from typing import List, Optional


class Solution:
    def FindKthToTail(self, pHead: "Optional[ListNode]", k: int) -> "Optional[ListNode]":
        # 第一趟：量长度。k 可达 1e9 而链表只有 1e5，绝不能拿 k 当循环次数
        n = 0
        p = pHead
        while p:
            n += 1
            p = p.next
        if k > n:                   # 长度不足 k，题面要求返回长度为 0 的链表
            return None
        # 第二趟：倒数第 k 个即正数第 n-k+1 个，从表头走 n-k 步即可到达；
        # k == 0 时走满 n 步落在 None，正好交出空表
        p = pHead
        for _ in range(n - k):
            p = p.next
        return p

BM8 链表中倒数最后k个结点¶