1.题目描述
2.解题思路（Python版）
方法一：遍历两次
思路：
1.首先计算链表的长度L；
2.第二次开始从头依次遍历，找到链表的第（L-k+1)个节点，即为所找的节点。
参考代码：
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
# write code here
Length = self.GetListLength(pHead) #计算链表长度
if Length < k: #如果所查找的点超过链表长度，返回一个空链表
return None
KthNode = pHead
for i in range(Length - k): #循环(L-k)次后，指向第(L-k+1)个节点
KthNode = KthNode.next
return KthNode
#定义计算链表长度的函数
def GetListLength(self , pHead:ListNode):
ListLength = 0
pNode = pHead
while pNode:
ListLength = ListLength + 1
pNode = pNode.next
return ListLength
复杂度：
时间复杂度O(N):N为链表的长度，对链表做了两次遍历，第一次遍历长度为N，第二次遍历长度为(N-k+1)。
空间复杂度O(1):在遍历过程中没有借助额外的辅助空间。
方法二：双指针法（只用遍历一次）
思路：
1.定义两个指针，第一个指针从链表的头指针开始遍历，向前走(k-1)步，第二个指针保持不动；
2.从第k步开始，第二个指针也开始从链表的头指针开始遍历；
3.由于两个指针之间的距离始终为(k-1)步，因此当第一个指针到达链表尾节点时，第二个指针刚好指向第k个节点。
4.需要考虑的特殊情况：(1)原始链表为空；(2)k=0；(3)k大于链表的长度。在代码中需要增加对以上三种特殊情况的处理。
参考代码：
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
# write code here
if pHead is None or k == 0: #如果链表为空或者k=0
return None
AheadNode = pHead #先出发的指针
BehindNode = pHead #后出发的指针
for i in range(k - 1): #快指针先走（k-1)步
if AheadNode.next: #还没到第k个节点，链表就已经遍历完了
AheadNode = AheadNode.next
else:
return None
while AheadNode.next: #一直遍历到原始链表的尾节点
AheadNode = AheadNode.next
BehindNode = BehindNode.next
return BehindNode复杂度：
时间复杂度O(N):N为链表的长度，两个指针只对链表做了一次遍历。
空间复杂度O(1):在遍历过程中没有借助额外的辅助空间。
3.重要知识点
（1）在动手写代码之前先分析当前思路的复杂度，并与面试官沟通对方期望的解法限制条件；
（2）注重代码的鲁棒性，尤其是对于特殊输入实例，自己要在代码中预设对特殊情况的解决方案。
标签：遍历,ListNode,offer,Python,self,链表,pHead,指针 From： https://blog.csdn.net/weixin_50335953/article/details/140082639