数据结构 已知一个带有表头结点的单链表,结点结构为 data link 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的 算法,查找链表中倒数第k个位置

为了在一个给定头节点的单链表中找到倒数第 k 个元素，我们可以采用双指针策略，这通常被称为“快慢指针”（Floyd's Tortoise and Hare Algorithm）。以下是算法步骤：

1. **初始化两个指针**：设置两个指针，初始都指向头节点，记作 slow 指针和 fast 指针。

2. **移动快慢指针**：fast 指针每次前进两步，slow 指针每次前进一步。当 fast 指针到达链表尾部（即 fast 和 slow 相遇时），因为 fast 先走了 k 步，此时 slow 指向的就是倒数第 (k+1) 个节点。

3. **再移动一次 slow 指针**：由于我们想要的是倒数第 k 个节点，所以需要从相遇点往回移动 slow 指针，直到它走到倒数第 k 个节点。

这里需要注意，如果链表长度小于 k+1，那么不存在倒数第 k 个节点，这种情况下返回 null 或 None 即可。

以下是伪代码描述：

def find_kth_to_last(list, k):
    if not list or k <= 0:
        return None

    # 快慢指针初始化
    slow = list.head
    fast = list.head

    # 当快慢指针相遇时，慢指针位于倒数第 (k+1) 个位置
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

    # 如果链长小于 k+1，返回 None
    if not fast:
        return None

    # 回溯 k 步找到倒数第 k 个节点
    for _ in range(k):
        slow = slow.next

    return slow.data