链表中倒数第k个节点

**链表中倒数第 k 个节点**

在链表数据结构中，链表是一种线性数据结构，每个元素称为一个结点（node），每个结点都包含一个值以及一个指向下一个结点的引用。链表中的元素可以按照任意顺序排列。

在某些情况下，我们需要找到链表中倒数第 k 个节点，这意味着我们需要从链表的末尾开始，往前找 k 个结点。这种问题经常出现在链表操作和算法设计中。

**解决方案**

为了解决这个问题，我们可以使用以下方法：

1. **首先遍历链表，计算链表长度**：我们可以先将链表中的所有元素都存储在一个数组或列表中，然后计算链表的长度。这样做后，我们就可以直接找到倒数第 k 个节点。
2. **使用两个指针来实现**：我们可以使用两个指针，一个从链表头部开始，另一个从链表尾部开始。每次移动两个指针，都向前移动 k-1 个结点。这样做后，我们就可以找到倒数第 k 个节点。

下面是使用两个指针来实现的代码示例：

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef findKthNode(head, k):
 # 检查链表是否为空 if not head:
 return None # 初始化两个指针 p1 = head p2 = head # 移动p2指针，向前移动k-1个结点 for _ in range(k -1):
 if not p2.next:
 return None p2 = p2.next # 移动两个指针，直到p2指向链表尾部 while p2.next:
 p1 = p1.next p2 = p2.next # 返回倒数第k个节点 return p1# 测试代码head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

print(findKthNode(head,2).val) # 输出：3