如何查找链表中倒数第k个节点

要查找链表中倒数第k个节点，我们可以使用两个指针的方法。以下是算法的基本步骤：

1. 创建两个指针，都指向链表的头部。

2. 将第一个指针向前移动k个节点。

3. 当第一个指针到达链表的末尾时，第二个指针就指向了倒数第k个节点。

以下是使用Python实现该算法的代码：

```python

class ListNode:

def __init__(self, value=0, next=None):

self.value = value

self.next = next

def find_kth_to_last(head, k):

初始化两个指针

first = head

second = head

移动第一个指针，使其前进k个节点

for _ in range(k):

if first is None:

return None 如果链表长度小于k，则返回None

first = first.next

移动两个指针，直到第一个指针到达链表末尾

while first:

first = first.next

second = second.next

第二个指针现在指向倒数第k个节点

return second

测试代码

创建链表 1 -> 2 -> 3 -> 4 -> 5

node5 = ListNode(5)

node4 = ListNode(4, node5)

node3 = ListNode(3, node4)

node2 = ListNode(2, node3)

node1 = ListNode(1, node2)

查找倒数第3个节点

k = 3

result = find_kth_to_last(node1, k)

if result:

print(f"倒数第{k