每日一题——链表中倒数最后k个结点

**每日一题——链表中倒数最后k个结点**

在链表数据结构中，倒数最后 k 个结点是一个经常遇到的问题。这个问题的要求是：给定一个链表和一个整数 k，我们需要找到链表中从末尾开始往前数 k 个结点所指向的元素。

**解决方案**

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

1. **双指针法**：我们可以维护两个指针，分别指向链表的头部和尾部。然后，我们可以将第一个指针移动 k 步，这样它就指向了链表中倒数最后 k 个结点所在的位置。
2. **栈法**：我们可以使用一个栈来存储链表中的元素，然后从栈顶开始取出 k 个元素。

下面是双指针法和栈法的具体实现：

### 双指针法

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef findLastKNode(head, k):
 # 检查链表是否为空或k是否为0 if not head or k ==0:
 return None # 初始化两个指针，分别指向头部和尾部 first = head second = head # 将第一个指针移动k步 for _ in range(k):
 if not second.next:
 return None second = second.next # 将第二个指针移动到链表的尾部 while second.next:
 first = first.next second = second.next # 返回倒数最后 k 个结点所在的位置 return first# 测试代码head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

k =2result = findLastKNode(head, k)
if result:
 print(result.val) # 输出：4else:
 print("None")

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef findLastKNode(head, k):
 # 检查链表是否为空或k是否为0 if not head or k ==0:
 return None # 初始化一个栈来存储链表中的元素 stack = []
 # 将链表中的元素压入栈中 while head:
 stack.append(head)
 head = head.next # 从栈顶开始取出 k 个元素 for _ in range(k):
 if not stack:
 return None stack.pop()
 # 返回倒数最后 k 个结点所在的位置 return stack[-1]

# 测试代码head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

k =2result = findLastKNode(head, k)
if result:
 print(result.val) # 输出：4else:
 print("None")