在链表中查找倒数第K个节点的技巧

# 1. 链表的基本概念和操作

链表是一种线性数据结构，由一组节点组成，每个节点包含数据和指向下一个节点的指针。链表提供了高效的插入和删除操作，使其成为处理动态数据集合的理想选择。

链表的节点通常包含两个字段：`data` 和 `next`。`data` 字段存储节点的数据，而 `next` 字段指向下一个节点。链表的第一个节点称为头节点，最后一个节点的 `next` 字段指向 `null`。

链表的基本操作包括：

- **插入：** 在链表的特定位置插入一个新节点。
- **删除：** 从链表中删除一个节点。
- **遍历：** 逐个访问链表中的节点。

# 2. 链表中查找倒数第K个节点的理论基础

### 2.1 链表的遍历和反转

**链表遍历**

链表遍历是指从链表的头节点开始，依次访问每个节点，直到到达尾节点。遍历链表可以使用递归或迭代两种方法。

**递归遍历**

def traverse_recursively(head):
    if head is None:
        return

    # 访问当前节点
    print(head.data)

    # 递归遍历下一个节点
    traverse_recursively(head.next)

**迭代遍历**

def traverse_iteratively(head):
    while head is not None:
        # 访问当前节点
        print(head.data)

        # 移动到下一个节点
        head = head.next

**链表反转**

链表反转是指将链表中节点的顺序颠倒。反转链表可以使用递归或迭代两种方法。

**递归反转**

def reverse_recursively(head):
    if head is None or head.next is None:
        return head

    # 反转链表的剩余部分
    new_head = reverse_recursively(head.next)

    # 将当前节点插入反转后的链表
    head.next.next = head
    head.next = None

    return new_head

**迭代反转**

def reverse_iteratively(head):
    prev = None
    current = head

    while current is not None:
        # 保存下一个节点
        next_node = current.next

        # 将当前节点指向前一个节点
        current.next = prev

        # 更新前一个节点和当前节点
        prev = current
        current = next_node

    return prev

### 2.2 快慢指针法

快慢指针法是一种用于查找链表中倒数第K个节点的算法。该算法使用两个指针，一个快指针和一个慢指针，快指针比慢指针先移动K步。然后，快慢指针同时移动，直到快指针到达尾节点。此时，慢指针所指的节点就是倒数第K个节点。

def find_kth_node_from_end_using_two_pointers(head, k):
    # 创建快慢指针
    fast_ptr = head
    slow_ptr = head

    # 快指针先移动K步
    for _ in range(k):
        fast_ptr = fast_ptr.next

    # 快慢指针同时移动
    while fast_ptr is not None:
        fast_ptr = fast_ptr.next
        slow_ptr = slow_ptr.next

    # 此时，slow_ptr所指的节点就是倒数第K个节点
    return slow_ptr

# 3. 链表中查找倒数第K个节点的实践实现

### 3.1 遍历法

遍历法是一种简单直接的方法，其基本思路是：

1. 从链表头结点开始遍历链表。
2. 每遍历一个节点，将当前节点计数器加 1。
3. 当计数器等于 K 时，当前节点即为倒数第 K 个节点。

def find_kth_to_last_by_traverse(head, k):
    """
    遍历法查找链表中倒数第 K 个节点

    :param head: 链表头结点
    :param k: 倒数第 K 个节点
    :return: 倒数第 K 个节点
    """
    if not head or k <= 0:
        retu