TikTok 单向链表倒数第五：双指针间距和长度不足

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练链表无环、长度有限，给头指针，倒数第一指尾节点。
• k默认5，k≤0非法，长度不足抛IndexError；只返回值，不改变节点连接。

解题路线

1. 单向链表节点有value与next，没有按位置随机访问。插删已知节点附近可常量，但找到某个位置仍需沿next前进，不能把所有链表操作都说成O(1)。
2. 双指针先都指头，fast预先前进k步。若期间遇空，长度小于k；这一步必须在主循环之前判定，避免后面slow为空时再取值。
3. 之后两者同步前進，直到fast为None。fast比slow领先k条next跳转，因此fast位于链末之外时，slow位于倒数第k节点。
4. 以0基位置表示，长度n，预移fast位置k，同步n−k次后slow位置n−k，正是倒数k。n=k时不进入主循环，直接返回头节点。
5. 两遍方案先计n再走n−k也正确，仍线性但两次走链。双指针适合只需一次持续推进、未知长度且只允许常量额外空间的情形。
6. 若输入可能有环，应先检测或定义拒绝，不然fast不会到None。示例按题目合同假设无环，不能额外称它已自动支持所有恶意结构。

手动走一遍

1→2→3→4→5→6→7，fast先走5步到6，再同步两次到None，slow到3。五节点时答案头；四节点时长度不足，不能返回随便某节点。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from dataclasses import dataclass

@dataclass
class Node:
    value: object
    next: object = None


def kth_from_end(head, k=5):
    if type(k) is not int or k <= 0:
        raise ValueError('k must be positive')
    fast = slow = head
    for _ in range(k):
        if fast is None:
            raise IndexError('list shorter than k')
        fast = fast.next
    while fast is not None:
        fast = fast.next
        slow = slow.next
    return slow.value

复杂度

O(n)时间，O(1)工作空间；只返回value，value自身对象大小不算新增复制。

易错点与追问

容易失分的边界

• fast预移k−1却仍用fast is not None循环。
• 长度不足不处理。
• 按value去重导致重复值链表错误。

继续深挖

• 若要求返回节点或删除它怎样改？
• 环检测与倒数语义有什么关系？
• 一次查询多个k如何权衡？