难度: Easy
给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
示例 1：
输入：head = [2,4,7,8], cnt = 1 输出：8
提示：
1 <= head.length <= 1000 <= head[i] <= 1001 <= cnt <= head.length
Submission
运行时间: 44 ms
内存: 14.8 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if head is None:
return
s = f = head
for _ in range(k):
f = f.next
if f is None:
return head
while f.next:
s = s.next
f = f.next
return s.next
Explain
此题解采用的是快慢指针的技术来找到链表中的倒数第k个节点。首先，定义两个指针s（慢指针）和f（快指针），均指向链表的头节点。首先移动快指针f，让其向前移动k个节点。此时，快慢指针之间相隔k个节点。接着同时移动快慢两个指针，直到快指针到达链表的末尾。此时，慢指针s将指向链表中的倒数第k个节点。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if head is None: # 如果链表为空，直接返回None
return
s = f = head # 初始化快慢指针都指向头节点
for _ in range(k): # 先移动快指针k步
f = f.next
if f is None: # 如果快指针f移动k步后到达了链表末尾，即k等于链表长度
return head # 返回头节点，因为需要返回倒数第k个节点
while f.next: # 当快指针f没有到达链表末尾时
s = s.next # 同时移动快慢指针
f = f.next
return s.next # 快指针到达末尾时，慢指针的下一个节点即为所求的倒数第k个节点
Explore
当快指针f先移动k步后，慢指针s开始从头节点出发移动。此时两个指针之间保持k个节点的距离。当快指针f到达链表的末尾节点时（即f.next为None），慢指针s正好停在倒数第k+1个节点上，因此s的下一个节点（s.next）是倒数第k个节点。这是由快慢指针之间的相对位置决定的。
在这种情况下，不需要检查头节点后是否还有其他节点。如果链表长度正好等于k，根据题目要求找倒数第k个节点，该节点就是头节点本身，无论链表后面是否还有其他节点。因为快指针移动k步后将指向None，这标志着链表末尾，慢指针正好指向头节点。
是的，确实需要处理k值非法的情况。如果k为负数，这在逻辑上没有意义，需要返回None或抛出异常。如果k大于链表长度，快指针在尝试移动k步时会因为找不到足够的节点而指向None，这种情况应当在代码中进行检查，并作出相应处理（返回None或错误信息），避免运行时错误。
为了确保不会在链表长度小于k的情况下访问空指针，应在快指针移动过程中检查其是否为None。如果在完成k步移动之前快指针变为None，这意味着链表长度小于k。此时应停止操作并根据具体情况处理，比如返回None或抛出异常。这种检查可以确保代码的健壮性和错误处理的正确性。