刷题记录：链表中倒数最后k个结点

刷题快刷魔怔了，上来就是哈希表
代码如下：

def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
    hashtable = dict()
    i = 1
    p = pHead
    while p:                        # 将每个结点存入哈希表
        hashtable[i] = p
        p = p.next
        i += 1

    if i - k in hashtable:          # 然后寻找倒数第 k 个
        return hashtable[i - k]
    else:
        return None

然后我仔细思考了一下
发现遍历一遍链表好像也没什么
代码如下：

def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
    p = pHead
    i = 0
    while p:            # 先遍历链表，确定结点个数
        p = p.next
        i += 1

    if i - k < 0:       # 判断倒数第 k 个结点是否存在
        return None

    p = pHead           # 遍历至倒数第 k 个结点
    for _ in range(i - k):
        p = p.next

    return p

怎么说呢，O(n + n - k) 也是 O(n)（滑稽）
写到这还没完
我相信自己肯定没题解快

遂观评论区
习得快慢指针
代码如下：

def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
    slow, fast = pHead, pHead

    for _ in range(k):          # 先令快指针走 k 步
        if fast:
            fast = fast.next
        else:                   # 若 fast 空则返回空
            return None

    while fast:                 # fast 领跑 k 步
        slow = slow.next        # 当 fast 为 None 时
        fast = fast.next        # slow 恰好为倒数第 k 个结点

    return slow

妙啊
接下来该魔怔快慢指针了